2 linux boxen not talking

I have 2 linux boxes that both have public IPs. They can both talk to the
Internet(HTTP, telnet, ping, ftp, etc), but they wont talk to each other. I
ran across this problem before and If I remember right it was a
misconfiguration of some sort, but I cant remember. Also, if I ping one
from the other it will get one returned and the rest will fail. Any ideas?

John Albee