Never heard of this problem before, but i would try uninstalling both versions of Firefox if you still have both installed and then reinstall 3.6.
I still wonder how come it broke my connection though... I mean, why only when clicking on google search results and not any other place
Anyway, thank you for the help, people!
Now I'm off to google "FF4 google issues" Happy to be able to do that