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.