Off the top of my head, I’ve had responses tweeted back to me from Charisma Carpenter, Don Trahan (golf pro), and Dan McRae (lacrosse player). I’m being followed by Edward James Olmos, but to be fair, he follows anyone and everyone who follows him. So that’s kinda cool. 
I’ve had a few…
Dee Snider responded to one of my tweets
Had a short interaction with Melissa Joan Hart
I’ve had a few longer conversations with Jane Wiedlin (of the GoGo’s)
I had a brief Twitter conversation with Penn Jillette once.
Nothing on Twitter, but I’ve only been there a couple months. Still figuring out the etiquette.
The closest I’ve had to a celebrity internet encounter was more than ten years ago. Slate used to do a feature called The Breakfast Table. They’d get a group of people who were in some way related (the same field of interest, or something like that) and they’d correspond over the course of a week about whatever was catching their attention. I responded to something in the Monday column and one of them quoted me on Friday saying it was the funniest thing he’d read in years.
Penn Jillette is my coolest one too. I sent him a link to a TwitPic Of Liam Payne (from One Direction) holding a 3 of clubs (P&Ts signature “force” card) and he Retweeted it saying “Oh I love this!” and favorited it. (I know his daughter is about the right age to be a fan and took a chance he’d recognize who it was.)
Back when Rich Fields used to be the announcer on the Price is Right we used to chat back and forth a bit. I made him a scarf that year for Xmas. :o
Yoko Ono used to do a Q&A once a week or so and once she answered one of my questions in a typically haughty and dismissive manner. Let me tell you it does nothing for your self esteem to be dissed by Yoko Ono. She follows me back but I’m assuming she does to everyone.
Sometimes the celebrities get a better reply than they were expecting, too. 
(Rio Ferdinand, Manchester United and England footballer and not underpaid, for the uninitiated…)
I haven’t tweeted much at all but I once sent an email to Bruce Campbell (his personal email was on his website at the time) and he responded.
Don’t tweet, but I’ve corresponded via email with each and every member of Country Joe and The Fish. They are great guys - truly.
Like anyone will know who they are, ya bunch of youngsters. 
Peter Sagal ("Wait Wait Don’t Tell Me) replied to a comment I’d made on one of his tweets.
That’s it for me, though.
Have you seen Shemar Moore? He could babble nonsense syllables and it would be fine. 
COOOOOOL! I’m gonna say I’ve had positive and negative interactions with famous people (various ages) and for the most part they’re good folk and really appreciate their fans.
I most likely was replied to by a Morrissey impersonator, but he’s a strange guy so I suppose there’s the slim possibility it was him. Not holding my breath though.
Other than that, the company I bought my glasses from replied to me when I tweeted that this is cute: http://www.warbybarker.com/, but that’s about it. I don’t really tweet to or follow any celebrities.
Asked Josh from Top Chef if people notice he looks like a fictional character. He told me people were calling him that while in Alaska. He was also unsure if it was a compliment. (It was, and the character was Yukon Cornelius from Rudolph the Red-Nosed Reindeer)
Don’t ask me, I don’t give a damn. My next stop is Vietnam. 
Someone I follow went to SD for Valentine’s Day. She “favorited” my comment gushing how cute they are together.
Lon MCeachern told me that Norman might play either the Stud/8 or Omaha event. And Lon’s plan depend on schedule and how well he did at Bay 101 (bankroll and momentum I assume)
Not a huge celebrity, but comic book artist Tony Harris has answered two of my tweets. The first one was when he posted a preview of an illustration, and I said it was “beautiful as always”, not expecting a reply. I’m not sure what he replied because I got the white question mark in a black diamond error message of doom. The second time he was auctioning a pic off on e-bay, and it said he was only shipping within the US (I’m in Australia), so I tweeted him to confirm it, and he responded that he would ship anywhere. I ended up missing out, anyway. So, kind of boring, but I was happy about the replies.
Bill Simmons
Darrell from “Storage Wars”
Armando Montolongo from “Flip This House.”
Some local radio guys as well.
Neil Gaiman answered a question I asked him via Twitter.
This nice little exchange happened today.
@jamesianster: just started here after long resistance. hope this will meet live up to expectations. (His first, and so far only, tweet)
@stephenfry: .@jamesianster Well, as it happens you were my 5 million 5 hundred thousandth follower, so welcome to twitter and I hope you have fun
