Oh boy, that sounds like a bug. If you have the full version (which I presume you do since you made it to the desert) then the desert key should work just fine despite the message. Sorry, will put this on the highest priority fix list!
Edit: Issue fixed in V1.0.3!