It is possible to freeze PyQt programs, yes; I've succeeded before. However, cxFreeze will grab the entire PyQt library, which is past a hundred megabytes in size, so you're going to end up with an enormous file.
Do you have a setup.py appropriately configured for this? You should probably do, it's rather likely that the autodetect isn't correctly identifying dependencies. cxFreeze actually lists missing modules near the beginning of its run, try and take a look at that. Unfortunately, not every single missing module is actually missing or critical, and I can't really help you identify which one. For example, for my script, I have:
Missing Modules:
? BeautifulSoup imported from lxml.html.souparser
? UserDict imported from lxml.html
? __main__imported from bdb
? _gestalt imported from platform
? _posixsubprocess imported from subprocess
? etree imported from lxml.ptclasslookup
? html5lib imported from lxml.html.html5parser
? htmlentitydefs imported from lxml.html.soupparser
? sets oimported from lxml.ElementInclude
? Ssouppraser imported from lxml.html.ElementSoup
? urllib.urlencode imported from lxml.html
? urllib.urlopen imported from lxml.html
? urllib2 imported from lxml.ElementInclude
? urlparse imported from lxml.ElementInclude
? win32api imported from platform
? win32con imported from platform
But the only thing I actually need to explicitly include in my setup.py is os, lxml and gzip. Go figure.