I don't think you have a problem with the NAT thing (since you aren't really using it). I believe you have a routing problem.

Have you configured it with RIP, OSPF, EGRP or something like it?
Yes, it's a firewall, but it's a Cisco, so it's a router at heart ;-)

I've taken a CCNA course at school (twice even), but it's really rusty... Never got around to taking the actual Exam either.
Anyway, whenever we experienced the problem it seems you have, it was because we had [censored] something up in the routing stuff.