The main problem with implementing your own NAT traversal (apart from just that this is very complicated) is that every NAT is slightly different. There isn't any one single algorithm that you just code up and then it works: instead you have to tune your code for hundreds of different NAT behaviors, build up a giant database of how NAT systems from different vendors work, design heuristics to detect what kind of NAT (or NATs) you are behind, then figure out how to tweak your algorithms so they work slightly differently from one NAT to another.
This is not fun, not sexy, and requires a huge testing lab to get access to all the different hardware and network configurations.
There is a good reason why there are so few successful NAT traversal implementations out there today! The one provided by LIVE is the best I know of, and that wasn't exactly cheap to develop :-)