For those of you who are still using Asterisk 1.4, I finally found a "fix" that works (and explains why some people haven't had success with a similar fix).
1. Either configure all of your external SIP trunks using IP addresses, or add the names and IP addressses of your SIP trunk providers to your hosts file, i.e.
cd /etc
nano hosts
add:
55.11.22.11
www.yourprovider.com
(replacing 55.11.22.11 with your SIP providers IP and
www.yourprovider.com with the name you use in the trunk configuration).
You'll need to make similar entries for all external SIP trunks that you use.
Save and Exit (Ctrl-O, Ctrl-x).
2. Ensure that your SIP Settings are correct in Asterisk. Go to the FreePBX GUI. Click on Tools, and then Asterisk SIP Settings. Look at the "NAT Settings" section.
You'll notice that, by default, NAT appears to be set at "Yes" and "External IP" is Blank. In reality, however, none of these items are set in the relevant .conf files until you make a change here and then submit the changes.
Set the NAT Settings, IP Configuration, External IP, and Local Networks properly and click submit.
A typical set-up is like this:
IP Configuration: Dynamic
External IP: yourdomain.com (get one free at dyndns.org)
Local Networks: 192.168.1.0/255.255.255.0
The key here, I think, is that Asterisk knows which IPs are local to you so that it won't attempt reverse DNS queries for all of your phones. If you don't have that set correctly, the problems will continue.
You may also be able to get by with:
NAT: No.
IP Configuration: Public
However, this may break other features (especially remote extensions).
When you're done, go the command line and type:
amportal restart