Spyware and other malware will sometimes cause unexpected problems with applications. I don't know of any specific issues we've had, but I know checking for/cleaning up spyware is one of the first things our tech support people have users do if they're running into problems.
I've never run into issues with Antivirus software, but I have had problems with firewalls (both software and hardware). Some software firewalls are poorly written and can cause problems even when turned off (looking at you McAffee). Some hardware firewalls/proxies can also cause issues. I believe we had a problem where someone's corporate proxy was filtering the data that went through it, which included modifying payloads if it found "bad" content. Sometimes our (binary) data would trigger that and would get modified, making it invalid by the time it reached the client.
Yahoo Messenger caused some problems with our app one time as well. It used some embedded flash movies to display ads, and something they were doing with Flash was breaking it in other contexts (our Flash app would fail randomly when Yahoo messenger was installed).
Real Player 11 beta also caused a lot of issues with our Flash application (intercepted network communication and broke the protocol in certain instances, among other issues), though I think they ironed them out before the final release.
To expand on Roundcrisis's comment, we did see problems in Vista as well. Depending on what your application actually does, changes made to the OS for Vista could cause problems.
I had to make some significant changes to one of our DLLs to make it work nicely in Vista. Also, the new application security stuff can cause problems with certain types of operations. If you're looking for things you need to test against, definitely test against Vista.