So the answer is yes. GPS does work without SIM card. However, I needed to do the following. I added Advance Systems Menu Patch and this actually allowed me to use a GPS locating app (which without GPS did not work, even though it was set in Location Services). The reason Google Maps did not work is that during setup I did not allow them to use my services.
So the bottom line is this. Use the Advanced System Menu patch if you are having issues with GPS!