Managed to fix it
Right...
2 days of my life in testing, testing, testing, restoring, and testing finally paid off.., so I'm going to save others the trouble and share how I did it. And before I start, to the attention of the forum mods, I'm writing this in good intentions. If I accidentally mention anything illegal, please remove that part and not the whole solution
Note: I'm assuming you have an iPhone 3GS and upgrading to iOS 4.0.1, but any other devices/version with the same symptoms should also work with these instructions.
So, I noticed that, if you upgrade from version X to 4.0.1, jailbreaking will
not work. Some rouge files will still exist in the device that will cause JBM to crash safari on install.
Don't bother with all this "clear safari history" crap. It wont work due to the problem above...
Don't bother restarting 100 times.. it will not help.
Don't believe what forums say about "oh the server is overloaded!! that's why it crashes!". A month later and I still see the problem. It's not related.
Don't bother visiting the mirror jailbreakme.modmyi.com thinking it's better.. it just redirects to jailbreakme.com...
What you
should do is not give up

Read on and I hope this helps others. The solution is, when you upgrade to 4.0.1, do it via the "Restore + new iphone" method. So many got it close.. like when they suggested the Restore, but forgot to mention the new iphone settings bit..

Steps below:
- Backup your iDevice in iTunes (apps, songs, contacts, etc..)
- Download the OS version you want to upgrade to from HERE (in my example, 4.0.1)
- In iTunes, hold down Shift in Windows, or Alt in Mac and click Restore, and select the image. If you're having trouble or if it errors out trying to restore, you need to follow the very easy instructions here in Windows or for Mac OSX.
- When done upgrading, it should activate and if all good, it should give you a message: "your phone is now active"
This is where some make a mistake. If you unplug now, again your JBM won't work. I strongly believe there still are old files/settings in there. So, proceed below:
- Keep your device plugged in, and iTunes will ask you if you want to restore your data. Do NOT. Instead, set it up as a new iPhone, call it anything like "testing iphone".
- Now you have a clean vanilla install, before you visit JBM, go to Settings -> Safari, and disable block popups, so that you can see popups.
- Visit jailbreakme.com on your device's Safari, and now it should work! =D
- You can now start restoring your iPhone's original backup.
Post Jailbreak problems:
Q. Help! I try to restore my files but I'm getting error Ex8008001!
A. That's because
appsync isn't installed. Make sure to reinstall
Installous which will also install
appsync. Just go to Cydia > Manage > Portals, and add
cydia.hackulo.us and search for
installous (with an o, not a zero).
Finally, right click on the iphone in iTunes, and
Restore From Backup.
Make a cup of tea, and when done, you're back to normal on a new version
I hope this helps others, and if it does look like the best solution out there, please spread the word.