The Universal Jailbreak needs another step:
After the "You are Jailbroken" file appeared, my "Update Your Kindle" menu option was still grayed out after I copied an update install package to my touch (fw 5.0.4). I needed another restart not listed in the jailbreak instructions before the "Update Your Kindle" menu option worked.
So, I suggest adding another restart AFTER the "You are Jailbroken" file is installed. This should help avoid some confusion...
EDIT: This universal jailbreak is nice. It has a lot more restarts and other steps than using my simple one-step "secret" jailbreak, but we are saving that for when we need it, and as long as this "more complicated" method is well-documented and people follow the instructions, it will do the job just fine.
Also, after I installed the new diags partition that comes on new kindles, I am happy to say that the universal jailbreak recommended in this thread works fine on it too (except for the extra restart needed before any packages can be installed).