Well, since you can see the Format and select Curency, I've got to figure you're almost there. The only reason I can thing why the format isn't changing is that the cell is already populated, and with an incompatible data type.
For instance, if it has date & time, duration, or text in the cell, you can't change it to currency.
To check, double tap on the cell. The cell data keyboard will come up. There are four icons on the left. From left to right they are Numbers, Time/Duration, Text, and Formula. To change to a currency format the cell data must be Numbers. That makes sense, yes.
Just change the data and you'll have no problem changing the format.
You can change empty cells to anything you want. So selecting the cell and deleting the content will also let you change the format.
Let me know if it doesn't work for you.
Edit: Hee hee, in this case the answer to everything was '42'. Which is the icon for number entry, in case you didn't notice. [Not so obscure reference to Hitchhikers Guide to the Galexy by Douglas Adams]