Presence thinks that you connect to the internet like this:
What's Wrong?
For Presence to work, you have to be able to connect from the internet to your Mac. Both your router and your modem are acting as firewalls, blocking connections from the internet.
Presence has successfully configured your router to let through connections to Presence, but your modem is still stopping them. You shouldn't have two firewalls.
What Do I Do?
Because you shouldn't have two firewalls, we need to tell your modem to let through all connections. You will still be protected because your router/Airport is a firewall.
Unfortunately, each brand of modem is different and so instructions cannot be listed here. You will need to read the manual for your modem. This will be available on the manufacturer's web site if you don't have it.
You are looking for a section in the manual that tells you how to specify a DMZ (try doing a Find for "DMZ"). This is sometimes also called "default server" or something similar. It's often in a section titled "Port Forwarding" or "Port Mapping". You should enter your router's IP address as the DMZ - this means all connections will be sent to your router, which is what we want.
Make sure you get the correct IP address:
You can see your router's IP addresses by going into its admin interface. (If you have an Airport, use Airport Utility.) Routers have two IP addresses - you want to find the one under a heading called "WAN", "Internet" or "Public".