I've had success with the following approach (John Smithenstien) is the example username:

1. Create <fi><ln(6-chars)>. (jsmithe)
2. If this is taken, query the DB (once) for records matching jsmithe\d+, finding the largest value for \d+ (say, we find jsmithe1 through jsmithe7, so the value is 7)
3. Add one to the value from the previous step. (8)
4. Append value to username (jsmithe8).

This requires two queries and one update to the DB, at most. It implements a rule that is easily understood and guarantees no duplicates. Obviously, there are many variations on this simple rule, but it's best to keep the approach straight-forward.