Yes, it is the NAT that is messing you up.
I've done this setup a few times, and every time I end up pulling my hair out - it's a b*tch to get configured correctly. You have to set up static routes on the VPN server so the traffic knows how to get back to the client. When a machine is NATted, you can send a request to it with no problem, but the response can't find its way back through your router. (That's why you can connect to it, but it won't authenticate.)
Since you're using a Cisco router, you can program the router to send the request back out, but don't ask me how to do that - you're going to have to find someone that knows more about routers than I do...
Your other option (that I usually end up doing) is using a live IP address for the VPN server, if you have one available.