I think your upgrade is awesome!
Interesting info about the "Skip to Main Content!" I had no idea about that.
For the nav links--"Home," "Services," "Site Map" and "Contact"--I would underline them only on mouseover because most Web surfers these days should know that those are the nav links. That is just me though, so do it the way you want!