I'm having the same problem with Google Maps. It eventually (couple of minutes) starts tracking.
As a test, install Microsoft Bing, and see how quickly it starts tracking.
Another alternative is to launch the GPS Status & Toolbox app and use the Manage A-GPS State option to manually initialize/reset the GPS before launching Google Maps.
Some of the apps that came with the phone never updated untill I downloaded appbrain and updated with that idk if that was just a bug but mays well try