Great news everyone. yellowsn0w 0.9.6 was just released. It works much better, and in the words of planetbeing:

Well, the new yellowsn0w works on all the SIMs we have around to test it on, at least.

Update from Cydia now!  I’ve gotten tons of e-mails from T-Mobile USA users that stated that my previous post wasn’t working for them.  The Airplane mode toggle would just make the “Searching” flash - like it wasn’t searching at all for a network.  My iPhone 3G is still working perfect, and I just got a new T-Mo SIM today.

Don’t forget to submit feedback to the iphone-dev team about your yellowsn0w experience.

update:

Do not forget:

Toggle 3G off by going to Settings > Network > Enable 3G [off]

My phone still worked with 3G on, but I didn’t test data.  I have the T-Mobile $19.99 total internet plan.