Question : routing nightmare - new pix install replacing an old GnatBox

Ok...I am out of ideas here...maybe somone has seen this before.
New Pix install just 2 ethernet ports in use (Inside, Outside).
Using a full class C NAT Pool and I have verified that the last PAT address is not being used.  I am running about 200 outbound connections in the xlate.
DNS is working...
WWW is working - I can browse to this web site or any other and enter a question such as this
Outbound traffic on the surface seems good.
All Inbound is working as specified in my access-list/static mappings.

Problem1:  Some internal PC's can not telnet to a customer IP and some can.  
My PC ... I can ping the IP, but I cannot telnet to it
User on my lan...  can telnet and ping the IP.
Same subnet, same gateway, same DHCP serves both.
PIX SYSLOG:  for my connection it shows connection attempt going out...then times out
Verified that the customer is allowing our full class-c inbound

Problem2:  Some internal PC's can not telnet to a customer IP and some can...A little different issue though...
My PC..when a tracerout is run to the customer IP, it goes to stars before it shows my pix or external router...it is like it is dieing on the inside?
My User's PC---connects just fine.
This is a different customer site, but it has also been verified that they are allowing the full class-c subnet inbound.

This is by far one of the strangest problems that I have delt with.  The PIX seems to be working just fine...out of 20 or more customers that we telnet/vpn to, we are only having this problem with a couple of customers.  I would automatically asume that it is the customer side if it was not for the tracerout issue in Problem#2.

Any insight would be appreciated.  

Answer : routing nightmare - new pix install replacing an old GnatBox

you're sure the customer is allowing your entire class C net with the telnet port open?