I never used to get this (I have the same phone, IOS and so on) but now I increasingly do.
Some journeys it doesn't happen at all, others I'm plagued by it.
Sometimes just leaving it alone is all I have to do and it fixes itself. Other times powering off the phone and on again kind of helps for a while.
I also quite often lose GPS lock when I turn a corner. This is when the view will change to different satellites, I assume.
I just assumed that it's because the GPS in the iPhone 3GS is a bit rubbish, and my phone is getting old.
I think comparing with Google maps can be a bit misleading because that also uses WiFi and 3GS signals, whereas I don't know if Waze does that?