Type incompatibilities converting char to uuid

I'm trying to upsize my legacy 35-character non-standard UUIDs to the
native 36-character Postgres implementation in 8.3. I thought some
ALTER kung-fu could accomplish this but my test bed is failing with
incompatible types:

CREATE TABLE uuidtest (
uidTest CHAR(35) NOT NULL PRIMARY KEY
) WITHOUT OIDS;

INSERT INTO uuidtest VALUES ('C5F25CC3-1D72-822B-795706E5A2C8F6B1');
INSERT INTO uuidtest VALUES ('A5F01CC3-1D72-822B-795706E5A2C8F6B1');
INSERT INTO uuidtest VALUES ('D6F25CC3-1D72-822B-795706E5A2C8F6B1');

CREATE TABLE uuidtest_ref (
uidTest CHAR(35) NOT NULL REFERENCES uuidtest(uidTest) ON UPDATE
CASCADE ON DELETE CASCADE
) WITHOUT OIDS;

INSERT INTO uuidtest_ref VALUES ('C5F25CC3-1D72-822B-795706E5A2C8F6B1');
INSERT INTO uuidtest_ref VALUES ('A5F01CC3-1D72-822B-795706E5A2C8F6B1');

Then try to convert them:

ALTER TABLE uuidtest ALTER COLUMN uidTest TYPE uuid USING
CAST(regexp_replace(uidTest, '([A-Z0-9]{4})([A-Z0-9]{12})', '\\1-\\2')
AS uuid);
ALTER TABLE uuidtest_ref ALTER COLUMN uidTest TYPE uuid USING
CAST(regexp_replace(uidTest, '([A-Z0-9]{4})([A-Z0-9]{12})', '\\1-\\2')
AS uuid);

And I get:

ERROR: foreign key constraint "uuidtest_ref_uidtest_fkey" cannot be
implemented
SQL state: 42804
Detail: Key columns "uidtest" and "uidtest" are of incompatible types:
character and uuid.

I have tried wrapping those two ALTER TABLEs in a combination of
transaction blocks, deferred constraints, disabled triggers, etc without
luck. I tried explicitly marking the FK DEFERRABLE but that didn't seem
to fix things. It seems from the CVS that this should be possible:

http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/tablecmds.c?rev=1.274;content-type=text%2Fx-cvsweb-markup

/*
* Foreign key constraints are checked in a final pass, since (a) it’s
* generally best to examine each one separately, and (b) it’s at least
* theoretically possible that we have changed both relations of the
* foreign key, and we’d better have finished both rewrites before we try
* to read the tables.
*/

But perhaps this is checking the values as opposed to the data types?

I'm trying not to delete and recreate all of my foreign keys if I can
help it for simplicity sake... any suggestions otherwise?

Brian