I have been a user of AVG Anti-Virus for quite a while and AVG recently released version 8.0 First, I think version 8 rocks; it has anti-spyware, anti-rootkit, and a Web Shield product. However, it is the Web Shield product that is causing a problem for some people with Windows Live Messenger. After installing AVG 8.0, attempts to log into Messenger are met with error code 8100030d, which says the service is temporarily unavailable.
The answer is to disable the "Instant Messaging protection" option in AVG. Messenger will then work properly, although the AVG system tray icon will complain that AVG is not fully operational.
Fortunately, AVG is aware of this issue. I emailed their support and got the following reply: "Please note that we are aware of this issue and our developers has already prepared fix. [sic] It will be available in the next program update."