Portqry is the tool we use for this, really great tool to check ports. Then if the provider is telling you they are open you can show them that they are not
http://support.microsoft.com/default.aspx/kb/310456
How to Use Portqry to Troubleshoot Active Directory Connectivity Issues
Another set of tools that can be helpful are netmon and/or wireshark. Packet captures with those tools can also really help you figure out what is going on.
Thanks
Mike