Apparently there's a special event that can happen you can be invited to (looks like one of those events like the "special night at the bar" type of things, where an NPC invites you to go over the phone. Called Meet A Celebrity, wherein it's apparently much easier to successfully introduce yourself (I wonder if this event can happen organically in the background from going to the up and coming lounge in Del Sol Valley? That's where I remember having the most success with introducing, personally... then again, maybe I was successful for other reasons). Apart from that, it looks like the main factors in success or failure are difference in fame level, mood of the celeb (positive a good thing, negative not), and fame perks networking perk. Surprisingly, charisma doesn't seem to be a factor at all. I would have thought it would be, but I guess not.
