Are the fullsize file names being inserted into the database even when it gets to that high of a number?
One thing you can do is to have 2 different directories for the regular size and thumbnails and then name them the same way. This way you won't have to go and remove the t_ from the thumbnail name.
Was it anything over 59 that wasn't working correctly? Could you try copying the images back into that directory and try uploading the image again to see if that was the actual cause?