I think you are trying to go a little bit too deep here. While it's great to read rails source and understand how the things work, mocking every instance of class used internally by Rails is not a good idea. In this case, UniquenessValidator, as opposed to some other validators, does depend on the database, so you should:
a. allow yourself to hit the database. it's not a huge overhead in such case and probably the most pragmatic way of getting this done. you even use "duplicate record" in comments inside your spec, so why not have a record there? In 9 out of 10 cases this is the right approach. After all you are checking a kind of ActiveRecord::Base object.
b. check behavior independent of rails validation. should do this anyway to test your preferred format of slug. its better to make sure default slug is valid before validation. the downside here is, that there is a tiny chance that before this call and the actual validation, slug will be taken by someone else, but it's the same with Rails built in validation so I wouldn't worry about it - you will end up with error, next try will be most likely successful.
it "modifies the beginning of the slug on validation if there is a duplicate" do
Profile.stub(:slug_exists?).with("bob-greenfield").and_return(true)
Profile.stub(:slug_exists?).with("1-bob-greenfield").and_return(true)
Profile.stub(:slug_exists?).with("2-bob-greenfield").and_return(false)
subject.set_default_slug_from_name
subject.slug.should == "2-bob-greenfield"
end
and you already know that Rails calls before validation so you don't have to test this behavior.
Also, it's best to make sure you have constraint on the database, Rails uniqueness is not enough: http://robots.thoughtbot.com/the-perils-of-uniqueness-validations