Can you print out the config (excluding the ips of course)?
How many external ip's do you have? Its not recommended to PAT to the outside interface. Also, do you any outbound policies?
The reason I ask is because the PIX, though they hide it, can only PAT around 4000 simu connects.
-ne1secure?