Although the Uniqueidentifier data type is only 16 bytes, adding one to an existing table could cause havoc. Say that you had a million rows in the table, you've just added 16MB of data, 2K pages at a time. This could cause a lot of page splits.

Use DBCC SHOWCONTIG to determine if you've caused the table to be serverly fragmented. Look at the value returned for SCAN DENSITY. A value closer to 100 is better.

-Mike