Those stars are used to indicate favorite contacts. Think of it like your top 10, your speed dial, or something similar. If the star is yellow, they'll appear on the favorites list in your contacts. If it's plain grey, the contact won't.
That star also appears in the browser for bookmarks I think.