Hey, just wanted to say it seems to have fixed itself. The antenna on my wireless adapter (it's not USB, but a PCI card) was placed at a bad angle.
Updating without errors for 4 hours already

And here's what the Windows internet connection sharing setup looks like:
http://4.ii.gl/cWQH7e.png http://2.ii.gl/VcyOp6.png