Ever change the smoothing angle to the left of the smooth button to a lower angle value? I see from the pic that it's maxed. I think it means that angles 180 and less will not be smoothed. (I could be wrong, since I usually don't mess with that setting and just hit smooth.) Try dragging it down to 90 and see if it works.

---

Barbequed Pixels?

Your friendly neighborhood Wings3D nut.
Also feel free to browse my freebies at ShareCG.
There might be something worth downloading.