I'd have to say NAT/PAT alone is not your problem. I have 1500 users being PAT'ed the same way, and the CPU doesn't run above 20% at peak. That's not to say you don't have something else going on there, but it's not real likely the PAT issue.
Quick way to tell is to do a "show proc cpu" (or depending on IOS version, a "show proc cpu hist"). That tends to be very enlightening. Of course, you could be running into routing issues related to your PAT scheme too, but I'd tend to look elsewhere first.
