I watched your video, as I also have the iPhone 3G, however, it's been in a full case since I got it. I've been running iOS 4 since WWDC and it hasn't ever exhibited the dropped bars problem.http://www.youtube.com/watch?v=84Lpt2YkF3Q
Video quality isn't HD yet since I just loaded it but the iPhone 3G has this issue as well.
So I agree with your assessment, it has to be a software issue.