Are your files actually in the location they need to be? Did you do the "mv oldshortname newshortname" part correctly? I just updated my document to be more explicit about that part.
If your files are where they should be in the Finder, then the problem is just in Spotlight. Go back to my User Tip and do the new Step 9 that shows how to reindex your home directory. I just tested the process and this will get All My Files working again. Thanks for finding that. Now I have a good reason to ask Apple to change their document but Apple's instructions would have the same result.