<p>I've searched for the solution to change the background color on the Compact Framework's MainMenu control, and the only answer I've found is that you need to create a custom control.  Does anyone have example code for this?</p>

There is no way of doing this.
Your right in that you'll probably need to create your own control.
This was something I was considering doing anyway to make the application go on Windows CE and Windows Mobile.
The problem with adding menus when the application needs to work with both is that the menu goes to the top of the screen on Windows CE and covers any controls that might be there.
It would be less hassle in the long run just make a new control.