OK, to clarify my story here, I already had an established iTunes account prior to getting the iPhone 3G. I purchased the phone on the second day it was released. Between then and last week, I had no billing issues and I could download whatever I wanted from iTunes - and during that time, I installed two applications, Facebook and Last.fm.
Last week when I got an email from iTunes about my billing, my app downloading was also suspended. However, I could still run Facebook and Last.fm. It wasn't until Monday or yesterday that I couldn't run either of those two programs.
The software update had no effect on my ability to run third-party apps. I was still out of luck both before and after the update. After the software install, I updated my Paypal information in the iTunes store (in order to re-download last.fm) and then after that, Facebook was working. It's possible that this is all just weird timing, but if someone else can test this, we can know for sure.