So I was talking my friend through putting his ps3 in the DMZ, when suddenly he was able to get an IP, but failed the Internet Test. Something about DNS error.
So I specified our own DNS Server (OpenDNS to be precise), instead of the router IP(well, the ISP DNS Server).
WE WERE ABLE TO CONNECT.
If you suffer from, or know anyone who suffers from "Unable to Connect to Host" when trying to invite a friend on Call of Duty 4, the solution is either in your router, or just on your PS3, specify an alternative DNS Server. We both set ours to the same, but as long as you use a DNS that isn't your router, you shouldnt have any problems.
Here is but a few you can use:
Service provider: ScrubIt
Public dns server address:
Dnsadvantage free dns server list:
OpenDNS free dns server list:
Service provider: vnsc-pri.sys.gtei.net
Public Name server IP address:
After Weeks of not being able to connect to each other, it has worked, and keeps working for us.