I have successfully downloaded and played the latest version of Warlords III Battlecry, and my friend has also. We would like to be able to play together online as we used to but can't.We both have Vista and can set up an online game, but when the other tries to find it there isn't anything there. Does anyone know a fix?

First suggestion: On both machines: Start a multiplayer game, then try alt+tab* to windows to see if you have a message about the program being blocked. Unblock to allow it.
*If alt+tab does not work, hit ctrl+alt+del and select the task-manager, that should allow you to access the block/unblock message window.

Unblocking the Windows firewall might help, but you're still going to have issues with your router.
The quickest and easiest solution is for you and your friend to just play WBC3 using GameRanger, which was designed to eliminate these problems automatically.