Do you have to have a reason, or just not like what is being proposed?

For example, if Al says: "Justine is a cat-burglar", can you challenge him simply because you wanted Justine to be a scientist? Or do challenges have to be rooted in conflict with established Facts?

The former absolutely. The Challenge (particularly the negotiation part) is one of the tools used to get other players to cooperate with your vision of how things should be. If want to see Justine be a scientist, you are limited only by your powers of persuasion during the the negotiation phase and how many Coins you have to outspend players who'd rather see her as a cat-burglar.

This is actually one of the game's key self righting mechanics. If you spend a bunch of Coins to do stuff (say Creating Justine was among them), you've had big impact on the game already. Now someone takes Justine and makes her a cat-burglar...and you don't have enough Coins left to win a Challenge...

So there is a built in motivation to both spend (to do stuff you want) but not completely outspend the other players (thereby becoming ineffectual in Challenges).

Conflict with established Facts makes it easier to Challenge, but are not a prerequisite. For example, if you'd spent a Coin to describe Justine as "law-abiding" than "cat-burglar" would be a contradiction of that and your Coins would be 2:1...plus you could likely count on support from players who don't really care except that they value consistancy.

Cool, thanks.