I got a lock after running the program but of course as soon as I started moving I lost the lock and was in la la land.
OK, I tried the navigation on the way home from work. It's still useless for navigation.

My drive is about 10 minutes long, first 5 minutes it just displayed a message "Searching For GPS...." Then it finally got a lock but updated way too slow. It was telling me to turn after I would already make that turn.
I bet you were both on battery only when you tried this, right?
Prior to GPSRestore, I had that issue when using GPS when the phone wasn't plugged into my car charger. Unplugged, if I got a GPS lock, then accuracy was iffy. Sometimes I got no lock at all. But once I put it on charger, instant lock, perfect accuracy.
I surmised that the problem may be that GPS is underpowered when on battery,which is different than bad GPS. I had tested this theory out plugged/unplugged (before the fix) and consistently, when unplugged, GPS had issues, either with locking or with accuracy.
After the Restore, GPS plugged remained perfect and unplugged was MUCH better, still not 100% as plugged, but lock was instant and, unplugged, accuracy went up to say 98% from 90%.
So, try the GPS *PLUGGED* and see if that improves your lock and accuracy while navigating. I'd bet that it will.
I've consistently stated I've had no issues from GPS since day 1. It was true, because I always plugged the charger in when I used my GPS. I only tried it unplugged because I figured that could be why there were so many complaints. And I was right, at least with my phone.
I have a detailed post about what I did to test this theory. I'll post a link when I've found it.
EDIT: Here's the link:
http://androidforums.com/samsung-captivate/221572-so-long-fellow-captivaters.html#post1913498