I have a personal and professional stake in computer security. A company I recently worked for as a tier 2 technician frequently had clients from an unnamed ISP (verizon...oops!) who had been instructing client to either deactivate firewall software (or in some cases with Windows XP to remove Service Pack 2 entirely). As a result I spent an average 2 hours per client removing various hijackers, keyloggers, worms, trojans and bots from their computers.
Eventually I grew tired of this and began recording the names of companies who did this, calling THEIR technicians and advising them that the client would call THEM (the technician personally) for assistance MANUALLY configuring the firewall to work with whatever software was having the problem.
DON'T BE ONE OF THESE PEOPLE. I do not slam the company in front of the client. But I give them very specific instructions on what to request from the third party...and the instruction to let me know if they need my help further. (Trust me, I can be a pain!

).
Therefore, manually configure their firewalls, or have your installation program do so. Your software is acting "suspicious" from the POV of the firewall and AV software. Microsoft Anti-spyware (beta) should be giving your users problems, since it sees unidentifiable, "unauthorized" access being attempted.
Good Luck.
****************************************
Excellence Breeds! Go Hard or Go Home.
Let Penguins rule the earth.
Break some windows today.