Trouble updating iPhone 3GS

Trouble updating iPhone 3GS

I have a jailbroken iPhone 3gs which runs iOS 4.1 (8B117). Predictably, I
can't download most of the apps and so often, I feel like it's not even an
smartphone. So I need to update it anyhow.
But everytime I try, I either receive Error 3194 or 3004. I've tried
numerous things suggested across various forums like removing the
gs.apple.com entry in the hosts file, putting it back, using TinyUmbrella
to do the same thing but all in vain. I have the latest iTunes version
installed (v.11). I've tried updating by just hitting Update/Restore, by
manually downloading the firmware and then doing Shift + Restore. I tried
by building a custom firmware from sn0wbreeze. I've even tried from
another computer. I've tried updating to multiple versions (5 and 6). But
nothing worked. I always receive either error 3194 or 3004.
I really need to update this. I'd be really really grateful for any kind
of help.
Thank you very much!