I didn't have this problem with my D1, but can't seem to find Google Maps in the market to download.
Try downloading and installing Appbrain and see if you can find it through that.
So is the Fascinate a worthy phone other than the Bing search issue??Any other Google apps that we wont have?
I went to a Verizon company store that had 2 working Fascinates. On one I found Google Maps in the marketplace but the other couldn't find it. Strange.
I also loaded GPS Test on 2 Incredibles, 1 DX and 2 Fascinates. Both Fascinates had trouble but all the other devices found 8-9 sats with good signals.