UUID index unused

I am assuming I am crazy and missing something completely obvious but I cannot get postgres (9.3.5) to use an index on
aUUID, ever.  

The main table has a natural composite key (2 uuids and a timestamp) with which it always uses the timestamp as the
indexcondition and filters on the UUIDs.  This occurs when when we do a query for a specific item comparing all 3 key
columnswith equality.  Other tables that have a single UUID column index also fail to ever utilize any available
indices;querying for a specific UUID always results in a table scan for them. 

Switching the UUID columns to text immediately solves the issues and index usage is as expected in all cases.

After hours of fiddling I figured it was time to ask.  Any ideas?

P.S.  Before it’s suggested… we have millions of independent devices generating the ids which drives our use of UUIDs.
Anythoughts of replacing them only result in us building something that’s basically a UUID to replace it.