When sorting you in a SharePoint Document Library you would expect it to behave as per Windows Explorer and in most cases it does. If you sort by a column (e.g. Name A-Z, Modified date) the Folders appear at the top followed by the Files.

After removing the "New folder" option from New menu on the library it changes so Folders are now in line with files - see illustration below.

My box has SP1 on but no further hot fixes so I can't comment if these would fix this issue.