1. Everybody who buys into it, including Roy Fielding himself, has to constantly say "no, that's not what I meant" and "you're not doing it right" if a REST service doesn't use HATEOAS. It reminds me of the response you get when you point out to college kids how bad Communism works out in the real world (see USSR, North Korea, et al): "No no no, it could really work, just nobody has done it right yet"
and 2: All the arguments eventually come back to an Appeal to Authority. "Well, Roy Fielding's dissertation says...". I sense that the real argument eventually comes down to whether a service can be called RESTful according to Fielding's dissertation, vs whether or not HATEOAS is actually a good idea.
--
A Rant follows. Disclaimer: I'm not an expert on the subject so feel free to correct me or anything.
The WWW itself is "RESTful". Even Hacker News is RESTful. You don't care about the URLs that show in your address bar. You don't construct them based on an ID-number on the side of each post. You just click around and submit forms.
With hypermedia, your consumer doesn't need to know about those specifics of URL construction. URLs are transparent. You just query for Resources and follow links.
YES, absolutely ZERO coupling is MUCH easier with boring CRUD-like stuff, such as Microsoft's OData, GData or AtomPub.
Maybe when you're writing a good consumer tuned for usability (like a Twitter client) you, app builder, will need to know some details on the service beforehand, but even then, having hypermedia would be cool. With a nice and pretty RESTful API, Twitter could just roll out new features, such as 'people who recently retweeted you' and you'd have a new section show up on your app instantly, since it discovers resources. Maybe you could even, like, load icons for new sections via links on the API itself...
Another example: I used to work on an App that used hypermedia: an Enterprise Content Manager with an OData API. Enterprise people used an decoupled enterprise client called Excel to connect to our Enterprise server and build random reports themselves.