How can I change the css classes on a menu's ul when it is placed in a particular region?
You don't need to change or add new classes because each region has already a class. You need to specifically reference each menu class () in your stylesheet by adding first your region class name:

#region-menu ul.menu li {display: inline...}

#region-sidebar-first ul.menu li {display: block...}

etc...


so check you won't interfere. 

Make sure the main menu has a unique reference as #region-menu to avoid inheritance.