It depends on how much info you have available at script time (such as a user ID) and what you're willing to do in regards to file names.
The increment file number approach works, but I think that might be a little more overhead then you need (you'd have to index the directory and find the last number used - not a problem if you have 10 files, but more so of a problem if you have 10,000 files).
If you have a way to identify the user or some way to identify the session (IP address?), great! Put it somewhere in there as the file name. If not, not a huge biggie.
I'd assume you'd have some sort of a base to the file name. You can be creative on this. Maybe "image" would work.
Then add a date part. You'd want to include the entire date/time info, but trim out everything that is not a number. You can do it pretty easily with the date function like this:
$mydate = date('Ymdhis');
$mydate will equal something like: 20031219130616 (you're time will vary). This is a unique number based on seconds. You could also use the Unix timestamp, but I'd think the number above is at least easier to read (you can tell its December 12, 2003 1:06pm).
Problem: If you have a super active site, its very likely you'll have people uploading images at the very same time. If so, this approach won't work too well. Thats where I'd suggest a unique identifier per user - its rather unlikely that they'd be able to upload 2 images within the same second. If you wanted to be careful about this (which I would recommend), I'd say just toss in there file_exists() on the destination before copying the file - if the file exists, pick a new time or add a number or something to the file to make it unique.
I've used this technique in the past and it works out very well. You end up with files like this:
image20031219130645.jpg
Kind of ugly, but they're nicely indexed (they'll sort very nicely) and you can still identify the time stamp for the file (not a big deal, but a handy feature for troubleshooting). Plus, there's not a lot of code required to make this work and PHP doesn't need to do a lot of indexing - it just needs to check if one file exists or not which its very quick about doing.
Of course, this is not the only way to make this work, but just an idea...