The START menu background is changed by switching to the Default Windows Mobile interface, with HTC Sense turned off. Then change the Today screen background picture. Turn HTC Sense back on and your START menu background will now be what you set it to.
Check this thread here:
http://forum.ppcgeeks.com/showthread.php?t=99188