Can I sequentially rename files in Linux?

You’re asking about a fairly straightforward shell script programming task, actually, which I think can be easily solved by recognizing that there are three basic steps:
1. create an ordered list of the files to rename
2. create a transformation formula that’ll turn old name –> new name
3. rename the old file appropriately
Agreed? Turns out your problem is remarkably similar to one I solved recently as part of how I manage the screen shot process when I’m writing articles here on Ask Dave Taylor. Until the latest dual-graphics-processor MacBook Pro arrived in the office, I was a long-time aficionado of Ambrosia Software’s Snapz Pro X, but on the new i5 and i7 core computers, the program forces the system to run the more powerful (read way more battery intensive) graphics subsystem. Long story short, I’m not using it any more and instead just use Cmd-Shift-3 to get full-screen captures that I later trim and edit.
The editing is no big deal, but the files are all named with cheery names like Screen shot 2010-06-13 at 5.24.58 PM, names that are non-descriptive and Web unfriendly. Instead, my image file names are more typically “reset-windows-live-password-1.png”, “reset-windows-live-password-2.png”, and so on. Useful, friendly, but not something I want to type over and over!
Since the Mac has a command line interface that is Posix compliant – no surprise given it’s running a variant of Linux under the hood – it turns out that the command line solution for my Mac will work for your Ubuntu Linux box too.
The first script step is to identify the matching files within a loop, so that each can be processed sequentially. In this case, it’s done with:

Simple enough, but we can’t always guarantee that alphabetical sorting is going to get oldest to newest files. Instead, a better solution is to use “ls -tr Screen*”, which returns the filenames in oldest-to-newest order. Sort of:

See what’s happened? Since we’re using the “ls” to order by creation time, the for loop just sees a lot of words separated by spaces.
One way to fix this is to actually change the file separator (shell variable FS), but I tend to like a different solution:

This replaces each space with a double underscore, ensuring that filenames survive the for loop intact. It’s trivial to reverse the substitution later in the script, as needed.
That’s the first piece nailed, and if you dont’ have any spaces in your original file names, of course, this can be simplified.
How about the second part, the pattern? To make my script as flexible as possible, I have the new pattern specified on the command line. To rename all the “Screen shot” files to ‘reset-windows-live-password-XX’, I simply specify the base name, knowing that the script appends an incrementing value to each filename:

The “count” variable will need to have an initial numeric value (I suggest “1”, but you could use whatever you want) but once “pattern” is set, that’s all I need.
Finally, the third step is the rename itself, which requires that I decode the filename:

Notice the use of the quotes: otherwise the “mv” command will fail when it sees filenames with spaces in them (yes, spaces really do make it a pain to work with filenames in shell scripts).
Let me put it all together so you can see the entire script now:

Now you can see all the pieces and how they work together. A quick demonstration:

That’s it. This should work just fine for your requirements too, and good luck to you!