Excel 2007 : Sorting Issues

I am editing a huge database that has been created in excel and is about 9800 entries.

I need the database to sort properly by last name and then by first name. When I select my data (there are 3 rows of "headers" at the top) and do the sort by First Name and then by Last Name, it catches all the last names, in the correct order, and then some of the first names, in the correct order, but then randomly decides to jumble some of the more common last names, such as Smith. Here's an example:

Smith, Andrew
Smith, Andrew
Smith, Andrew
Smith, Denise
Smith, Jason
Smith, Jason
Smith, Jason
Smith, Jason
Smith, Kellie
Smith, Andrew
etc (and then ir resorts properly within the next subset)

This problem does not happen on all entries, but enough to make manually moving then everytime I have resort a giant pain.

There are no blanks and all the cells are formatted the same. I'm stumped and am trying to meet a deadline for today, but if you know a solution and it is 3 weeks or longer from now PLEASE post it. I will inevitably run into this problem in the future.