As with many aspects of programming, Design Patterns misused become bad things (i.e., Anti-Patterns). Facade is no different. When Facade is used poorly, or improperly, it becomes a hindrence to good code, not a boon. Coat of Paint is one such anti-pattern that can come from bad Facades. (query: is there a generic Anti-Pattern name for misusing a Design Pattern?)
An example of coat of paint would be, say, a partial abstraction layer around SAX's DefaultHandler, where it might simplify some function calls for startElement, but still leave you with a (complex) SAX Attributes object instead of a simpler access class for that.
In other cases, a programmer might know that the abstraction of a particular API is desired and necessary, perhaps to support potential plugability (note, this comes in violation of XP's "You aren't going to need it", and suffers for it). So he designs his abstraction layer without consulting the other APIs its meant to plug in with. The result is either 1) he ends up writing much more complicated adapters for the other APIs to be plugged in, or 2) he has to refactor the whole abstraction layer (and fix ALL its references in the code its already used in).
E.g., Jakarta Commons Logging, which is still very useful, but does have a sign of this in stablizing the debug level constants on Log4J's set, and thus makes the adapters for SimpleLog and Java 1.4 Logging a little more complex; this is a minor thing, but in other cases may be a major stumbling block for extensibility and reuse.
Other coats of paint include (IMHO) any interface that exposes indexable properties in the form of (pre-generics) Collections rather than arrays. The paint may simplify some parts of the underlying system, but you still have to know the system in order to know what to cast to.
In other words, Facade used properly is a GoodThing(tm). Facade used poorly is a Coat-Of-Paint.
Utility Methods fit somewhere in between. Most of them are simple wrapper functions meant to avoid making the same N calls in a row, even as they do still expose some parts of the underlying classes. Most Utility Methods are really revealing that the underlying library is either incomplete, or needs to better support common use cases (see 3 Strikes rule).
If you can change the underlying library, refactor the 3 strikes condition into a new method. If you can't, then the utility method should remain.