Make Foo and foo to be different free tagging tags in Drupal 6
This goes beyond Drupal - your database is using a case-insensitive collation, so all queries are case-insensitive.

Changing the collation would be the way to sort it ("how" is out of scope here but easy to find on Google), but that might produce unwanted results. I'd advise taking a backup beore making any changes, and having a good read up on the whole collation concept before going any further.

Another approach might be to alter the individual queries that go into the txonomy_term_data table (using hook_query_alter()), and set the collation manually (SQL examples in the COLLATE docs above). Again, your mileage may vary so take a backup before trying anything.