One last thing that I can think of:
After checking to see if you can play Rock Band 1 songs, go out to the dashboard, go back into memory and delete the Lego Rock Band Export Key one more time after authenticating the Rock Band 1 license, Clear the System Cache Again and the redownload the Lego Rock Band Export Pack.
Come to think of it that, I didn't download the Lego Rock Band Export Pack until after I verified Rock Band 1 songs worked.
Sorry when I did it I wasn't writing the steps down, I was just trying something different.
Now you should be able to Export the songs.