Is your Location Service set to Battery Saving (i.e., the GPS radio turned off)?
Also, go to Settings>Location, tap Menu>Scanning, and make sure wi-fi scanning is turned off. This might also be in the Advanced Wi-fi menu (Settings>Wi-fi, tap Menu>Advanced). If this setting is on, it allows the phone to turn on wi-fi intermittently to try to get more location information from nearby wi-fi networks, even if you have wi-fi turned off.