Windows Update Error

Ok, I tried using the AVG uninstaller but that didn't fix the problem. I took my computer to a local library to make sure that it wasn't my internet that was acting goofy, but no dice. Any other suggestions?

So I think I kind of figured out a solution. Instead of clicking on check for updates, I clicked on "Check online for updates from Microsoft Update" and for some reason, that seemed to work. I have no idea what the difference is between "check for updates" and what I clicked but it went through. As relieved as I am, by having to manually click to get updates, I can't set my computer to check for updates automatically as I've done in the past. I'll obviously take this over not having any updates but it would be nice to be able to set up an auto check for updates. I attached an image if anyone doesn't know what exactly I mean by "Check online for updates from Microsoft Update".

Does this "solution" ring any bells as to what could be the real reason for windows update not working properly?

Thanks for all your help!

Is that common for most networks? I've tried on three different networks and I've had problems on all of them.

Sorry for the confusion, but what I meant was that I took my computer to 3 different places and it didn't work in any of those places. I tried it at my parents place, my apartment and my library. Also, my roommates computer's updates work perfectly fine in our apartment.