After much fiddling around I've finally got a route through the AVG 2011 Firewall.
Here's what to do.
1) Open the Firewall settings (obviously) and select "Defined networks" from your current active profile.
2) Click "Add network" and put in the name "IPv6Tunnel" (or whatever you want) and description.
3) Click "Add IP" and select "One IP address" then fill in the IPv4 tunnel server address from HE.
4) After ok-ing all the changes, now go to "System services" under the profile again.
5) Click "Manage user system rules" and click "Add".
6) For protocol, select under "Other known protocols" IPv6.
For direction, select "Both ways".
local ports & remote ports "All ports".
For remote address, select the network you created earlier "IPv6Tunnel" (located at the bottom of the list).
Name it "IPv6" or something you will remember.
7) Click ok to everything and now your HE tunnel should work.
I hope some people find this useful.