Hi Greg,
The first rendering is the normal behavior of the ASP.NET menu, it generates tables which are not sematically ideal for menus. It was a long standing complaint that MS later resolved by putting out the CSS Control adapters which could alter the rendering to be more semantically correct. The second rendering with ul and li elements is using the Control Adapter.
In mojoPortal Menus we use the Control Adapter version, but in order to make it possible for developers to also use the original menu rendering (in case they need it in their custom features), we did not extend the normal ASP.NET menu with the control adapter. Instead we created a sub class mojoMenu that inherits from ASP.NET Menu but uses the Control Adapter. So to get the nice rendering you need to inherit from mojoMenu, not ASP.NET Menu.
The mechanisim that hooks up the adapter to the mojoMenu is is the App_Browsers/CSSFriendly.browser file. I would look in that file with a text editor and see if there are differences between production and dev. Note however, that though this file is just xml, changes made to that file wll only take effect upon a re-compile of the solution.
Hope it helps,
Joe