1. Use SecureRandom.uuid instead of UUIDTools. 2. Belonging models should specify string type refering Site. 3. Apply Ruby 1.9 or higher syntax. ;-)

link.rb

# app/models/link.rb
class Link < ActiveRecord::Base
  belongs_to :site
end

migrations.rb

# db/migrate/20110422210841_create_sites.rb
# 1.  :id => false
# 2.  :uuid 
#
class CreateSites < ActiveRecord::Migration
  def self.up
    create_table :sites, id: false do |t|
      t.string :uuid, limit: 32, primary: true
      t.timestamps
    end
  end

  def self.down
    drop_table :sites
  end
end

migrations_for_belonging_model.rb

class CreateLinks < ActiveRecord::Migration
  def self.up
    create_table :links do |t|
      t.string :site_id, limit: 32
      t.timestamps
    end
    add_index :links, :site_id
  end

  def self.down
    drop_table :sites
  end
end

site.rb

# app/models/site.rb
class Site < ActiveRecord::Base
  include Extensions::UUID
  has_many :links
end

uuid.rb

# app/models/extensions/uuid.rb
#
module Extensions
  module UUID
    extend ActiveSupport::Concern

    included do
      self.primary_key = 'uuid'

      before_create :generate_uuid
      
      def generate_uuid
        self.id = SecureRandom.uuid.gsub(/-/, '')
      end
    end
  end
end

Are you sure primary: true is working? When I run your migration, the uuid column is nullable and the table has no primary key. I'm running Rails 3.2.13, and this happens with both mysql and sqlite. This is the generated table:

CREATE TABLE `sites` (
  `uuid` varchar(32) COLLATE utf8_unicode_ci DEFAULT NULL,
  `created_at` datetime NOT NULL,
  `updated_at` datetime NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;