I can download updates fine (just tried a few minutes ago).

You could download the update manually from http://www.grisoft.com/us/us_updt7.php then tell AVG to update from the folder you downloaded to instead of updating over the internet, or as Mirage said, enter the appropriate proxy settings into AVG if you know them (I guess you don't since you didn't know you were proxied).