Found this by trial and error on my 3G. Turns out the upgrade turns on Location Restriction. To re-enable location:
1) Go to Settings
2) Select General
3) Go to Restrictions
4) Either Disable Restrictions, or set Allow/Locations to ON.
Location should be re-enabled.
iPhone 3G iOS 4