Adam Lambert talks about Simon Cowell's exit from American Idol with Oprah

American Idol star Adam Lambert is finding these days that he's pretty famous — there are few places he can go where he isn't recognized. And despite all the notoriety surrounding him after his controversial appearance on the American Music Awards in November, he's comfortable with the fact that people are touched by his music.

"The biggest change between before 'Idol' and now would probably just have to be the level of notoriety. I mean, it changes everything," he told Oprah Winfrey on her show Tuesday (January 19). "I try to go throughout my daily life just as if nothing has changed, but you don't have much anonymity anymore, which feels really good. People come up, and say hi and they enjoy your work."

Even though he is appreciative of the mostly positive fan response, he told Oprah that in December, he started to feel the stress from his newfound fame. "I just kind of got a little stressed out, and I was taking it all very seriously and getting really nitpicky about things. I was really beating myself up about performances and how I looked and this and that," he explained. "As the year came to an end, [I realized] this is a once-in-a-lifetime opportunity. I need to enjoy this. This is amazing. I got what I wanted."

He recently also received advice from Madonna about how to handle fame when he met her briefly at her New York apartment last year.

"I said, 'I'm sorry, I'm sorry. I'm just really intimidated right now.' And she said, 'Why?' " he recalled. " 'Because I love you!' And she said, 'So love equals intimidation for you?' And I said, 'Yes, pretty much. Most of the time, I think, when I feel love, that's the way it manifests itself at first.'... [She said], 'Just keep your eye on the prize and put your blinders up,' " he added. " 'Don't get sidetracked with all the extra fuss.' "

Lambert, however, knows how to create headlines for himself, with the AMA performance or coming out in Rolling Stone magazine. or his American Music Awards performance — and he said he doesn't regret them, particularly the latter.

"I knew that label would be attached to me from there on out, and I think people would jump to conclusions with that label," he says. "I've seen a lot of press where they say, 'openly gay singer Adam Lambert.' It's like the gay part comes before the singer part, and I'm like, 'That doesn't define who I am.'"

As for Simon Cowell leaving "American Idol" after this season, Lambert, who placed second last season, admits that he's definitely going to be missed.

"I think the audience will definitely miss Simon, and I think the contestants will miss out on, like, really honest criticism," he said. "I think that that's important to making you a better performer — you've got to hear the good and the bad. He makes you step your game up and calls you out when it doesn't work. But I also think he's got a very specific taste. There's certain things he's not into, for example, country music. He doesn't like it ... I think that ultimately after the first couple weeks of auditions, the audience tunes in every week for the contestants. They grow fond of one or a couple of people. We tune in to hear the contestants blossom or not."

Adam Lambert to appear on special Oprah show?

Oprah Winfrey usually keeps the subject of future shows top secret -- but she may have tipped her hand yesterday about an upcoming Adam Lambert show.

On the "Share Your Story" page of her Web site yesterday, the show appeared to be hunting for fans of the "American Idol" runner-up for a show built around the controversial singer.

"Calling ALL Adam Lambert Fans!!!" the posting said.

"Did you vote for him as many times as you could? Were you holding your breath when the new American Idol was announced, hoping and praying it would be HIM?

"If you are a HUGE fan of Adam Lambert's, email us now and tell us why you want to be in the audience for this once-in-a-lifetime show," the solicitation read.

When Lambert was interviewed on the show briefly last October -- for an episode about reality TV stars -- the talk show host invited him back to perform after his CD was released.

This would appear to be the make-good on that invitation. Speculation seems to be January 29th - a birthday both stars share.

Adam Lambert and Randy Jackson on Oprah’s “Biggest Reality Stars” Show

Not even Oprah is immune to the charms of “American Idol” runner-up Adam Lambert. The singer will talk about his upcoming album (and its attention-getting cover art) on Thursday’s episode, which is all about the biggest stars of reality TV. Lambert will be joined by America’s Best Dance Crew, “Project Runway” alumnus Christian Siriano, Randy Jackson and even cake bakers. Tune in for show updates!

4:36 p.m. — Adam Lambert time! Wow — he’s only appearing via Skype. Adam can’t make it to Chicago to talk to Oprah? He says he’s still finishing up his album. He says being discovered is a thing of the past, which is why he auditioned for “Idol,” to build a base. He talks about being a chorus boy in “Wicked” — and how he’s a “rock star”! And his segment ends, with an introduction for Randy Jackson. Jackson says he was a little shocked Adam didn’t win. Adam says he had no idea what was going to happen, and that it didn’t matter at the end of the day, because he got what he wanted: an album.

4:43 p.m. — Jackson talks about all the changes, and Oprah says she’s excited about Ellen Degeneres starting as a judge for season nine next year. But that’s for another episode. Jackson starts to pimp his “night job” show, “America’s Best Dance Crew.” He says the idea for the show came from watching the International Hip Hop competition. Season four winners “We Are Heroes” perform; the all-girl crew perform a superhero-themed show in shiny spandex and with mini-torches. Ha — they are literally breathless when Oprah tries to talk to them. Not because they’re in awe, but because their routine knocked the breath out of them.