Have to say that I've been suffering from this too. I've tested it on three legs of my commute so far (also about an hour and mix of motorway / A roads) and each time the GPS has been pretty flakey. Seems ok for long stretches and then randomly drops out for minutes at a time (and this is with the phone sat on top of the dashboard in the middle with only the windscreen above it - and wide open road, blue skies etc.).
That said - it isn't really a fault of the Navigon software (although it does seem to be overly sensitive to GPS inaccuracy - it quite often thinks I've moved from the motorway to a parallel country road, despite there being no exits around for miles!), it's more the iPhone's GPS being a bit ropey - as I often suffer similar GPS issues with Google maps.
I find it curious that not many other people are reporting such GPS problems though - I may try a full restore on my handset and then load my apps back on as a new handset (when I first activated it I did a restore from my last 3G backup). Can't see how exactly, but perhaps my backup has somehow got slightly corrupted. I sync all my contacts and calendar via google so that shouldn't be an issue.
Dont suppose you're using a case on your iphone? I have a case on mine which might be affecting it. I'll try my journey home with the case off to see if that makes a difference.