I know it's possible to do this in the classic start menu, but wanted to know if the same could be done in the regular start menu.
It is possible, but "Enable dragging and dropping" must be checked/enabled.
In Windows XP: right-click the Start menu/Properties/"Start menu", press Customize/tab Advanced/check "Enable dragging and dropping"/OK/OK.
Now it is possible to sort by right-clicking on any item in "All Programs" and select "Sort" in the context menu.
(I have checked it on Windows XP, but not on Windows Vista or Windows 7. Please correct me if it does not work on those two platforms.)