We've both tried connecting to each other's IP address, but no luck. The connection keeps timing out.

Do you have your firewall set up so that CIV can get out? May just be a setting that needs to be adjusted.

Yea, the firewall ist usually the first guess in such a situation. Have you been able to connect to your friend's computer with other games? Can you ping your friend's IP address (assuming you know how to do that)?

There are actually a thousand other possibilities, depending on how much or how little you know about networking. For example, I've seen people trying to connect to their friends' private IP addresses.

We were able to connect before, though, and I haven't changed any settings in the meantime.

I also used whatismyip.com to get my real IP address, and as I said, it worked before. But now neither of us can connect.