Booleans are great...but they have limits too. It depends on the geo of both objects...they should have similar subdivisions....so trying to boolean a simple cube to a complex surface will not work. The geo will appear messed up because thats how Maya will interpolate divisions that are needed...these can be simply deleted or moved to better present the geo. I have found smoothing first and boolean..then no more smoothing will be needed or even try it...wont work. You really have to experiment....nothing better than experience will help you with booleans mate. I will post something similar in a short time
cheers bullet
bullet1968
"A Darkness at Sethanon", a book I aspire to model some of the charcters and scenes