I've got the exact same problem with Windows 2000 Advanced Server. If I share the connection (in Sharing tab of the connections properties) it works fine; but, I'm unable to duplicate that functionality through RRAS with NAT.
I'll try and remember to post any solutions I find/figure out.
-- Peter