I've just came across this error when using CriteriaBuilder.isNotEmpty() on an @ElementCollection with Hibernate 4.2.5, so please don't forget to fix the Criteria code for isEmpty/isNotEmpty as well.
As a workaround the size of the collection could be checked. CriteriaBuilder.exists() can't be used since a subquery is not allowed for Embeddable.