This is how I got my unlocked, jailbroken iOS 3 iPhone 3GS (Model
MC135LL, Baseband 05.12.01) updated to iOS 4.1.

I first followed the instructions on
http://iphoneblogr.com/2010/11/redsn0w-0-9-6b2-tutorial-pwned-dfu-mode-for-windows-users/
to install the pro-broken iOS 4.1 from
http://iphoneblogr.com/2010/10/pre-jailbroken-4-1-firmware/

This resulted in a jailbroken 4.1 that was not, however, unlocked any
more. But the simple video tutorial
http://www.youtube.com/watch?v=VsQJdAjHnHE shows how to perform that
last step with ultrasn0w. It seems to work fine now!