Same thing happened to me with a 1GB card using the same method as the OP. Hit X while trying to figure out what was wrong, and when I restarted the PSP it had a shiny new CFW waiting for me. Turns out the menu was there, just not shown. I'm still amazed how lucky I was to not brick my PSP by...