Are you able to pick up any wi-fi hotspots?
I've read how this works is Airport looks for SSIDs and compares them to a database of physical locations for known SSIDs that comes from various sources such as registered WiFi spots and even the Google Street View cars driving around mapping WiFi spots.
So if you're not near any wifi hotspots at all, or none with known physical locations, it doesn't know where you are.