The Nubis project had a requirement for a highly available network address transation (HA NAT) instance. There are a number of ways to solve this problem, but the solution found here: http://www.cakesolutions.net/teamblogs/making-aws-nat-instances-highly-available-without-the-compromises looked pretty good.
This repository is code based on the above solution, with a few tweaks.