firewall error in windows xp

Hi my brother-in-law is no longer able to surf the web.
When you try to log on with msn messenger 6.1 it says that
there is a firewall preventing him from logging on. He
does not use a firewall and it has not been checked off in
windows. He also cannot access any web sites. I have spent
a long time taking to the service provider, who says that
some limited info is getting to and from the computer as
the modem and ports seem to be working. We ran varies
tests through some of there software and they think it
might be a virus. I have run some virus detectors but have
found nothing, Any Ideas