I can eject mine if it's still charging. Mine's a Video but I don't know if it's different for a Shuffle. LOTR would probably know. Try going to the Shuffle support & search for that error you're getting, or try the iPod forum???
http://www.apple.com/support/ipodshuffle/

Is it still updating? I don't think you can eject while they're updating.