I knew about the GPS problems before purchasing the fascinate, and sure enough mine had the same problem. Then today a friend of mine told me to take out the battery and hold the power button for 30 seconds (with the battery out obviously). After that, put the battery back in and boot up.
Problem solved. GPS locked on my exact location in under 5 seconds, and it has NEVER done it before.
Worth a shot.
UPDATE: Possible GPS fix (has worked for me and others)! Download GPS Status from the market and let it run...it should fix the GPS problem. Credit goes to Sessionthree (post #5)!