Automatic type conversion

I'm in the process of attempting to upgrade from 8.1 to 8.4, and I've been using the uniqueidentifier contrib module for my UUID's ... In 8.1 Postgresql was able to figure out what to do with statements like

# SELECT 'Your new UUID is ' || newid();
                       ?column?
-------------------------------------------------------
 Your new UUID is 5f1a4987-9005-42d6-8e62-d1ff14bb1433
(1 row)

but in 8.4 (and probably 8.3 also...),

# SELECT 'Your new UUID is ' || newid();
ERROR:  operator is not unique: unknown || uniqueidentifier
LINE 1: SELECT 'Your new UUID is ' || newid();
                                   ^
HINT:  Could not choose a best candidate operator. You might need to add explicit type casts.

But, with the new internal UUID datatype, what is the magic recipe that allows this to run?

# SELECT 'Your new UUID is ' || uuid_generate_v4();
                       ?column?
-------------------------------------------------------
 Your new UUID is cd8d8f5f-3eea-4e96-be4f-f93daa174d8f
(1 row)
 
I could add the explicit type casts, but I'd rather find out what the nature of the subtle (or not-so-subtle) difference I've stumbled upon is...