This method will only work for iPhone 3G with bootloader version 5.08 (5.8)!
You can quickly check your bootloader version by using TinyUmbrella. Download it from here. It should show your bootloader version right away. The screenshot below shows an iPhone 3G with bootloader version 5.9. Alternatively, you can also try using f0recast [Windows or Mac] from ih8sn0w.com.
What you need:
Jailbroken iPhone 3G
Fuzzyband – install this from Cydia
afc2add – install this from Cydia although not necessary
i-Funbox – a file explorer for iPhone, Mac users can use DiskAid
6.15.00 certificate (download ICE2-06.15.00.cert) for Fuzzyband
Launch Fuzzyband after installing the app via Cydia.
Connect your iPhone to the computer.
Launch i-FunBox and select File, then go to Applications/Fuzzyband.app, right-click and then select Copy from PC.
Copy ICE2-06.15.00.cert you have downloaded earlier to this location
Go back to Fuzzyband and you can now begin the downgrade process. If the downgrade is successfully, you should see “I Haz Downgrade”
You can now unlock it with ultrasn0w.