It's actually why I left Debian for another distribution... I think that it may have also had a bad habit of overwriting /boot/grub/menu.lst every time that program was updated. That could have been Ubuntu, though. It was a dual-booter's nightmare! I had to boot from a live cd and fix way too often.
I think your menu.lst problem is neither Debian nor Ubuntu, but a change in management of that file by grub itself. Starting from grub 2.0 /boot/grub/menu.lst gets created from scratch on every update of grup, kernel or init.rd, using the parameters given in /etc/grub.d/ (in Debian). If you want to dual boot to another os, you have to place your commands there, and they'll find their way into menu.lst automatically on every kernel update.