The director wasn't so much of a problem, Terry Gilliam bought the rights from Pterry and Neil for the princely sum of one groat (still owed, from what I understand) and still owns them. The problem was more about finance. Terry Gilliam likes to make his films independently, but while he could raise most of the cash for the actual filming, he couldn't get Hollywood to agree to stump up for distribution and marketing. For the kind of budget Good Omens would have required ($45-50 million, US, as of five years ago), the financiers naturally wanted to see the film in multiplexes world wide in order to maximise the chances of a return on the investment. You don't do that without Hollywood on board, so the money melted away. It's a shame, because Terry Gilliam is probably the perfect man to film it.