Heh, I have that fear, too, about meeting celebrities I like (which, sadly, I've yet to have happen). I'm always afraid of coming off like a typical dork fan who says the same things they've heard a trillion times.
I've always liked these guys' music. I still remember when "Yellow" came out and I first saw that video. Then I remember hearing "Trouble", and later, "In My Place", when they came out, on a radio station I used to listen to at night sometimes, and I just thought those songs were so beautiful (still think that). When "The Scientist" came out, I completely fell in love with that one, and I started paying a lot more attention to the band.
However, for some reason, even though, over the years, I kept hearing all their singles and loving each and every one of them, it took me a long time before I actually brought an album of theirs. A friend finally sent me Parachutes, and that convinced me, so when Viva La Vida came out I picked that one up. That was the first album of theirs that I actually brought. My interest kept piquing, and then finally, their latest one came out, and in quick succession got that album as well as their second and third ones.
So...I guess, I've liked them for 11 years, but when my real "fandom" started, probably within the last few years, I'd say. 2008 or so, if I had to pinpoint it.