This is an FYI for anyone that searches for this topic that comes after me... or maybe some day if I forget. I was trying out Google's new native Symbian C++ implementation of gMaps yesterday - pleasantly surprised to see that it worked perfectly with my Bluetooth GPS I had synced long ago and had forgotten about - and I remembered that I hadn't looked to see if there was a new firmware for my Nokia e61 in probably over a year. So I swapped over to my Windows box, downloaded the firmware upgrade tool from Nokia, plugged in my phone and ran the updater.
I have to say that Nokia has come a LONG way in terms of it's software tools sophistication. The whole process was about a hundred times easier than any other Nokia application I remember installing on my Windows PC. That said, the firmware update stalled and eventually it told me it had failed and to try again. The problem is that the phone seemed completely bricked, so retrying the process wouldn't work as it couldn't even see that the phone was connected to the PC. Joy.
I was pretty confident that it wasn't bricked forever, and a quick search pulled up this forum thread on Nokia's Support site which, after a few pages, explained how to reset the firmware. I'm almost positive I played this game before, but I had completely forgotten.
Here's the magic instructions:
1. Unplug the charger and take out the battery, put the battery back in, but not the charger.
2. Hold the Green key, 3 and * keys down while you power it on. (The 3 and * are the same keys as the Y and U, you don't have to "shift" or anything, and remember that the Green key is *under* the left soft key. That got me for a bit until I wised up.)
3. It may take about 20 seconds for your phone to come back, keep holding all the keys and the power until it does. Hopefully you'll see, like I did, that the new firmware has been installed after all, and it was just sort of "stuck".
If this doesn't work, then probably your phone is fried for real and you'll have to send it to some support center somewhere to get it re-flashed, but it seems that's pretty rare, and more likely the process is just stalled for whatever reason.
Hope that helps someone. :-)