First, finding references on this is hard. Perhaps it's sufficient to say that rasulullah changed the names of certain people when their names were islamically unacceptable. See my answer on naming girls Asiya for some examples.
If you look through the sunnah, you won't find that rasulullah changed the names of anyone who had these names; you will find he changed Abdul 'Uzzah (the slave of Uzzah, one of the mushrikeen gods), or similar names, into Abdullah.
I put this question to my Arabic teacher; this is essentially what he said:
- Allah's names all have Alif-Laam at the beginning (eg. Ar-Rahman, Al-'Aleem).
- This prefix (alif-lam) makes a very strong form of the name; this prefix is unique to Allah alone
- You can name your sons without the prefix (eg. Ar-Raheem => Raheem)
- You cannot name your son "Rahman," because the meaning is unique and distinct from the other names (roughly translates to "the source of mercy")
- You can name your sons with "Abd" and the name of Allah (eg. Abd Ar-Rahman, commonly written as Abdur-Rahman)
Wallahu a'lam.
Source: Understanding Islam Arabic Course, circa 2005