As pointed by VMguru, MS does not support installing Exchange 2007 on a single-Labeled DNS Domain. MS Has pointed that even in their Exchange 2007 RTM, but it was possible to install the RTM in a single-Labeled DNS Domain which made the issue more critical for organizations who already implemented Exchange 2007 RTM on a single-Labeled DNS Domain as their domain has already been implemented and got integrated with Exchange 2007 which make it even harder to change the name of it.
If you are implementing a new setup, it will make a better sense to re-install Active directory or rename it before installing Exchange 2007 to be supported and avoid any future related issues with Exchange 2007.
If you have already implemented Exchange 2007 and trapped into the situation that you can't upgrade to SP1 as you have a single-Labeled DNS Domain you got the following options:
1- Build a new non single-labeled DNS Domain & Exchange 2007 and do a migration of your users and mailboxes to the new setup.
2- Build a new setup and start from scratch.
I know the above two solutions are neither great neither easy, but they are the only two ways available, as at the moment the rename tools used to rename windows 2003 domains are not supported when Exchange 2007 is installed. I hope Microsoft will release a new rename tool which will allow this, but no statments of Microsoft in that regard yet. It seems Microsoft not seeing it being their problem that people are not reading the pre-requisite quite well. Good luck with this and hope this help.
If any one got any update on this please post it up.