Add class to Menu Block UL unique to each Menu Block instance?
Unless your theme changes the usual behavior then each of your menu blocks will have its own unique ID so you can use CSS like this (note the ID/class I used here might not be the ones you have to use, they're just an example):

#block-menu-block-2 ul.menu


This way you don't have to worry about overriding the markup of the menu to add classes in.