I got the same error after a glitch. Turns out the redemption was successful the first time, but because the server was too slow responding to the redemption request, the App Store app timed out. For whatever bizarre reason, it appears that the app store server infrastructure doesn't treat redemption requests as idempotent (clearly a bug), so subsequent attempts to redeem the same code from the same account fail. Ideally, those subsequent attempts should do nothing, but should return whatever magic value tells the App Store app to update its list of purchased items and then do whatever other work it needs to do.
To make a long story short, if you quit the App Store app and relaunch it, the Yosemite beta should appear under the Purchases tab in the App Store. From there, you can start the download.