Clean Up By is only available in icon view. If Arrange By is not set to None, it doesn't seem to do anything until you change Arrange By to None. If Arrange By is set to None and Sort By is set to Snap to Grid, it arranges icons so that they are aligned on a grid. If Arrange By is set to None and Sort By is set to anything else, it sorts icons and changes Sort By to None.
The Arrange By modes were added in Lion. They group items under sections like this in different view modes:
List views cannot be sorted by clicking the headings when items are arranged by some attribute.
When items are arranged by some attribute, Sort By affects the way items are sorted inside the categories in some cases, but in other cases it's disabled.
Sort By doesn't group items under sections. The Sort by mode is changed when for example clicking the list headings in list view. The Arrange By menus change to Sort By when holding option: