I would create another column in the database called something like "slug" and make it a unique string. Now, when adding a new record, I'd generate the slug for this one.
I found an example for a function to create the slug as an answer to this question: PHP function to make slug (URL string)
The slugify-function, provided in the answer to the quoted question, does not check if the value already exists in your database. You'd have to do it yourself and add a suffix like "-1" if the slug already exists.
If you have done all that, your data should look similar to this:
Table Users
User_id    First_name    Last_name     Slug
   1          John         Smith     john-smith
   2          John         Smith    john-smith-1
   3          Kia          Dull       kia-dull
The next steps should be quite easy.
This would be an option to create the links:
<a href="<?php echo $row['Slug'] ?>"><?php echo $row['First_name'] ?> <?php echo $row['Last_name'] ?></a>
The .htaccess file should be fine like you have it already ...
RewriteEngine on
RewriteBase /
RewriteRule ^(.*)$ profile.php?uid=$1 [L]
And you just have to query the table for a value like $_GET['uid'] in your profile.php file. Now I'd rename the parameter uid into slug, because it's not longer an ID, but you can get the ID quite easily by querying after the slug.
Benefits of this solution:
- Easy to debug. The slug is something you can find 1:1 in the database. If you now have a URL you can tell, without guessing, which user it is.
- Consistent. Even if you'd delete the row with id=1, the row id=2 would still have the slug "john-smith-1"
FYI:
A slug is the part of a URL which identifies a page using human-readable keywords.
  http://en.wikipedia.org/wiki/Clean_URL#Slug