The upgrade took about 2 hr but went really smoothly.
Even though its probably possible to go from 5.0.4 FOSS to 5.0.13 NE, after reading the forums and seeing reccomendations I decided to upgrade from FOSS to FOSS first.
Once i tested that for a few mins, I decided the risk was minimal to go from FOSS to NE. This went very smoothly and we have a new shiny NE server.
I also have another server running 5.0.13 FOSS. Once you get through your DNS issues, everything goes very smoothly. On my FOSS server, I decided to use bind9 to help with the DNS. You can literally install a version of zimbra without messing around with your DNS server. This wiki entry really helped
Ubuntu 8.04 LTS Server (Hardy Heron) Install Guide - Zimbra :: Wiki