Ah yes, but what they did not tell you:

http://www.cd.cz/en/mezinarodni-cest...-evropa/-8984/

A certain number of tickets on each train are sold at a discount (so: 29 euros for a seat, 39 for 6-berth couchette, 69 for a 2-bed sleeper). They are only available at a CD international ticket counter. They can sell out, which puts you back to the fare they quoted you above.