Thank you all so much for your help.

Darkware, your orignial sugguestion did not work for me, but I might have been doind it worng. It kept trying to add polys which I don't want.

dannyngan: It was the normals. My model was orignally made from patches and I guess one of the patches had normals facing the wrong way so that's why it would not smooth shade from one forner patch to another. I just used conform to make sure all normals were uniform, and then set to face to make sure they were all pointing out from the center of their faces, and it looks nice now. (Well it's a crappy model, but it shades nicely) I did have to turn off the checkbox "Set User Normal".

However, (as with Darkware), Step 4 (Averaging normals) didn't seem to do anything good. It made 3/4 of my polys pure black, and the rest were flat gray.

:banana:

FYI, my file was in Maya 4.5