In the early 90s, you knew you'd arrived as a rock group the day you made it on to MTV and the Beavis & Butthead show. So it's 1993 and the joke is that Beavis has heard the song before, while Butthead hasn't. Over soft guitars, someone is singing in a baleful falsetto about a girl who makes him cry. Butthead is not alone in feeling impatient. 

Beavis: 'Don't worry Butthead, it gets cool in a minute.' 

Butthead: 'It better start rocking or I'll really give him something to cry about.' 

Beavis: 'Shut up Butthead, it's cool. Check it out, check it out! Here it comes...' 

[Metallic guitars ejaculate into a chorus of 'I'm a creep, I'm a weirdo, I don't belong here.'] 

Beavis: 'Yes! Yes!' 

Butthead: 'This is pretty cool.' 

Beavis: 'Yeah yeah yeah yeah.' 

Butthead: 'Uh?...Uhh?' 

[The soft guitars return.] 

Beavis: 'What... what's going on...? How come they don't just, like, play that cool part through the whole song?' 

Butthead: 'Well, Beavis, if they didn't have, like, a part of the song that sucked, then, it's like, the other part wouldn't be as cool.' 

Beavis: 'Really? You're pretty smart Butthead. Hey, here it comes again. Yes! Yes! Raaawk...!' 

By the end, they've observed that the singer seems a little low on self-esteem and have helpfully struck up a chant of 'I am somebody, I am somebody'. They are sending up Radiohead, five sallow public schoolboys from Oxford, and they will be neither the first nor the last. Back home, the single which broke them in the US, 'Creep', sank without trace on the first occasion of its release. The NME called them 'a lily-livered excuse for a rock band' ('and they may have had a point,' affable guitarist Ed O'Brien allows late one night in a Parisian hotel bar, seven years later). They were dismissed as a corporate-funded Nirvana-lite and eclipsed by the arrival of Suede, a home-grown rebuke to American grunge, who presaged Britpop and had everything Radiohead didn't; a clear raison d' être, a great first album and the support of the press. 

And Suede had a sexy singer. If John Osborne had been born 30 years after he was, there is no question he'd have chosen rock'n'roll over the theatre, and if you imagine the adenoidal playwright modified with a few genes from Richard III, you have the public face of Radiohead's singer circa 1993. Thom Yorke was born in October 1968, with the muscles in his left eye paralysed, a condition which demanded no less than five operations before the age of six. It can still be the case that when he turns his head to the side and fixes you with his cornflower-blue right eye, his left appears to be glaring at someone on the other side of the room, who's annoying him even more than you are. Strangely, this gives him a kind of presence and may be what drummer Phil Selway is referring to when he says that Yorke 'was very noticeable and always stood out in a crowd' at school. 

Needless to say, the singer was teased mercilessly when young and could be forgiven for being in a funk with the world, which he learnt from an early age to vent through his music. He was a fighter at school and there is often an undercurrent of rage and frustration in even his most reflective lyrics. He confirms that he still gets hate mail from fans he upset during his last tour. 'Being in a band is about wreaking revenge on the world,' he once conceded. 'It's like when you get chucked by your first girlfriend. You just say to yourself: "I'm going to be famous one day, and she'll regret that..."' 

Now we find Thom Yorke standing on a stage, inside a huge blue tent, with lights skittering across the angled surfaces above him and 10,000 rapt Parisians gazing at him from below. In the early days, you'd have got long odds on Radiohead being here, with two seminal albums under their belts, in the form of The Bends (1995) and OK Computer (1997). You'd have got longer odds on their fourth album, Kid A, which is released tomorrow, sparking the kind of critical discussion which hasn't been heard since the two European groups who changed pop - the Beatles and Kraftwerk - were at their peaks. Some critics are calling it a commercial suicide note. 

This is the second of two Parisian dates on a short European tour which involves two different tents leapfrogging each other across the continent. It's an enormous production and all the dates are sold out. At this particular moment toward the end of the show, Yorke is the only real focus. His voice brings to mind an angel being attacked by a swarm of bees and he spins a melody the way a spider spins a web, gossamer and intricate, allowing it to drift across a jackhammer electro beat which makes the floor judder and your scalp tingle. As lights strobe and guitarists O'Brien and Jonny Greenwood help to propel the song towards an urgent crescendo, Yorke starts to shudder and squirm as though someone's plugged him into the mains, as though caught up in religious ecstasy. It's an extraordinary moment and I've only ever heard a more fevered response to something a band has done once before - and Take That only had to walk on staage at Wembley to elicit that. 

The song is 'Idioteque' and tonight's audience have never heard it before, or anything like it. It's the eighth tune on Kid A and the most striking result of a creative crisis that afflicted the group and has taken the better part of two turbulent years to resolve. The trouble began with OK Computer, which is regarded, with a degree of unanimity as the finest British rock album of the past decade (closely followed by The Bends).

In its wake, the quintet were obliged to tour for a full 12 months, a process which they had been through with The Bends and nearly failed to recover from. This time, Yorke came back disenchanted with the guitar music he had been making and resolved to change it. Melody, he has said, came to seem like 'an embarrassment'. He wanted the emphasis to switch to rhythm. 'I just wasn't interested in guitar music anymore,' he will tell me, going on to deny any suggestions that bravery was involved in tearing Radiohead down and starting over again, saying, 'Yeah, but things were being torn down anyway. That's how I felt. There was no being brave. It was "I either do this or forget it. Just stop."' 

The frightening thing, Yorke will add, is that he saw no way out. He had always been the catalyst for Radiohead and there was no one else to take up the reins now. ('We operate like the UN,' he told one interviewer drily, 'and I'm America.') 

In February 1999, the five members convened in Paris for a month during which almost nothing was achieved. The same thing happened in Copenhagen later, during which time each individual member had begun to have doubts as to whether the less traditional, less methodical approach the singer was trying to foist on them could ever work - and even if it did, whether there would be a place for them within it. 

Yorke had played in a techno group called Flickernoise while studying art and English at Exeter University, but the electronic artists he was holding up as pointers to the way forward now (such as The Aphex Twin and Autechre) mostly worked on their own or in pairs. Nothing was happening and the band was insecure. On some of the tracks, none of them were being asked to contribute directly at all. Only three of the 10 pieces that would eventually comprise Kid A have any obvious guitar parts on them. Selway was not alone in realising that they had been together for 15 years and were essentially the same schoolboy band they'd started out as. But they weren't schoolboys anymore. 

Tensions rose until a series of blazing rows led to an acknowledgment that there was space for them all, even though they might not be playing their usual instruments on every track, and earlier this year the album began to take shape. The group were reputedly close to splitting up again in February over the issue of whether to pour all of the 23 tracks they'd recorded on to a double album, or whittle it down to a concise single disc. Once the brooding, piano-driven 'Everything In Its Right Place' had been chosen to open proceedings, the rest of the sequence followed naturally. At only 48 minutes long, Kid A was conceived of, and sounds like, a unitary piece of work, rather than a collection of songs. 

Radiohead will admit to eschewing photo shoots partly because they look so peculiar together. They range in height from Yorke's flyweight 5'7", to Ed O'Brien's hulking 6'5", and in age from drummer Selway's 33 to Jonny Greenwood's boyish 28. They met at Abingdon school in the Oxford suburbs and, Yorke excepted, are as articulate and easy-going a crew as you could hope to find anywhere.

I met the brothers Jonny and Colin Greenwood (guitar and bass, respectively) in a north London restaurant, where we chatted amiably about the obvious things, along with history (which Colin read at Peterhouse College, Cambridge), books and music. Jonny was at his most animated when describing the influence of composers Penderecki and Messiaen on his string arrangements for OK Computer and Kid A and Colin explained Radiohead's attitude to fame and success in a way that was unusually comprehensible. 

'I think, as long as you keep moving, you're all right,' he said. 'The thing is you're always developing and expanding. It's a protean thing and a public image can't keep pace with it. So it - the process of success - is like this slow-drying glue that sets around you, that slows you down and gums you up. And while all that's happening, your own life's going on at the side of it, with your own relationships and your own experiences and that becomes sort of calcified as well. And the whole thing just grinds to a halt really. And then you suddenly find yourself in the paper or on the cover of a magazine and your life and experiences have become summarised. And once its summarised, its over. So the trick is to try to be in the corner of people's vision, but not full on.' 

How much do you feel like rock stars, I'd asked? There had been a wary pause, before Jonny pitched in with 'I don't know. It feels like Radiohead are famous. But that no one knows who we are. Which is brilliant, really.' 

By the time we sit down to talk on the train from Paris to London, Thom Yorke has been a thorn in my side for several days. On the whole, he doesn't talk to the British press, because he feels misunderstood and misrepresented by them. He is annoyed by the accusations of miserabalism and implications that he is a spoilt middle-class charlatan. On the latter, he is vituperative. 

'The middle-class thing has never been relevant,' he spits. 'We live in Oxford, and in Oxford we're fucking lower class. The place is full of the most obnoxious, self-indulgent, self-righteous oiks on the fucking planet, and for us to be called middle class... well, no, actually. Be around on May Day when they all reel out of the pubs at five in the morning puking up and going "haw haw haw" and trying to hassle your girlfriend...' 

He has also been irked by assumptions that a song like 'Exit Music (For A Film)' from OK Computer is about suicide, and that an early number like Anyone Can Play Guitar is a sardonic swipe at the vacuity of being in a band, when it was intended as an innocent celebration. Phil Selway has protested that 'I've always seen our songs as being quite positive. They confront very painful topics, but at some time there's always a sense that there's a struggle with them and an attempt to overcome them.' Yorke, too, considers that he worked through a lot of his post-adolescent angst on the patchy first album, Pablo Honey, and changed through the making of The Bends, at which time he realised that 'there's a fine line between writing something with genuine emotional impact and turning into little idiots feeling sorry for ourselves and playing stadium rock'. 

The lyrics for Kid A will not be printed on the sleeve and Yorke has resisted even explaining them to the band. A few, like the refrain of 'You can try the best you can/ you can try the best you can/ the best you can is good enough' - a piece of advice his girlfriend freqquently offers him - on 'Optimistic', seem self-evident. Most do not. He describes the indiscernible words to the whispering electronic title track as 'the most vicious I've ever sung'. 

Yorke has been avoiding me to a degree that has begun to assume comic proportions and I'm marvelling at the extent to which people come to resemble their persecutors after a time, when word arrives that he will talk. 

When I finally settle into a seat opposite him, I find him disarmingly friendly, even warm. He smiles and laughs a lot, turning out to have a keen sense of humour. I ask why he is so fearful of these situations and he explains that he doesn't like having to answer for something that someone else has written. He no longer reads anything about himself, not even reviews of his records. 

We return to the turmoil that descended on Kid A. 

'When we finished the OK Computer tour, I had a sort of big... block. I basically thought that was it. I thought that I wouldn't be able to do whatever it is that I do again. We were still sort of working, but I had no faith in it. So I was in this endless cycle - and it was very much on my own as well, because we didn't see each other much for awhile. And I was doing bits and pieces, mucking around really. But in the process I was discovering that I'd lost all confidence in myself.' 

Why? You had just made two critically and commercially successful albums. What more did you want? 

'Yeah, but if you've lost faith in the way that you're going, then that's where you end up. I always used to use music as a way of moving on and dealing with things and I sort of felt like, that the thing that helped me deal with things had been sold to the highest bidder and I was simply doing its bidding. And I couldn't handle that. And that was all sort of wrapped up with feeling huge amounts of guilt about something that, when it was good, just came naturally anyway. So it all just went round and round in circles for ages. So there's no bravado about we're gonna shake this shit up, really. It's more like, I can't carry on like this.' 

Do you have any sympathy with the idea that rock has run its course and there's nothing left to do but trot out the tired cliches? 

'Oh yeah, absolutely. Totally. I 100 per cent agree with it.' 

But Radiohead are regarded as one of the few groups capable of taking it anywhere new. 

'God help us if we are. The thing I have a problem with is the fact that so much of what people - of what journalists - term rock music now is really not based on the music itself, but based on the lifestyle that goes with it. It's like a lifestyle choice... That doesn't mean that people should stop using drums and guitars, but why stand up and say, "I'm a rock star - in 10 years time I'm going to get fucked up on smack..." The mythology around it has run its course and is stale and uncreative now, and it has been destroying the people who've been trying to make the music. 

'I worry about that in the context of the album we've just done, as well. I absolutely want no part in any suggestions that our decision to use some electronic instruments is some kind of lifestyle choice. It's not. You use the instrument to help you get across a certain thing that you want to get across. That's all.' 

But haven't you often been hostage to the belief that you need to be in a state of turmoil to be creative? 

'No. No, I dealt with that one. I think the turmoil that is required is one that you can find any day walking down the street. I don't think you need to go and seek it out. Any normal human being goes through states of flux which they need to resolve by talking to people or making their art or whatever.' 

Would it be true to say that you have a generally pessimistic caste of mind, though? 

'No. I don't think so.' 

That's certainly your reputation. 

'Yeah, whatever. It depends what it's about. No I don't think like that at all, actually. For me, even when things are incredibly bleak in terms of the world you see reflected in the newspaper, I still sort of find you can get excited when you look in people's eyes when they walk down the street and sometimes you see really nasty, terrifying things, but most of the time you just see a bunch of people trying to get it together and there's something really hopeful in that. It sounds a bit bonkers, but there you go.' 

You've found touring tiresome and destructive in the past. Having seen it as close quarters, I'm constantly surprised that anyone with a modicum of sensitivity and/or intelligence survives that life for more than a year. 

'I don't think they do. I think they either step out, or they go pop.' 

Have you felt close to doing either of those things? 

'Oh, I did go pop.' He smiles broadly and gazes out of the window, chuckling. 'I definitely went pop.' 

How did this 'pop' manifest itself? 

'Oh it was a fairly quiet little pop, really. I was really... I saw this really cheesy Bruce Lee film, the story of his life. And there's this bit in it where he's standing between two mirrors and there's this break and he goes nuts and he has a seizure. Well it was like that without the seizure. It was just on and off really. I mean it wasn't like... it was just a state of mind. But in a way it was just kind of not knowing how to deal with it. And I look back now and I'm really quite happy that it happened, because it makes you decide what to do and then go on that path for awhile. And then you sort of pick yourself up and you carry on and you feel so much better that you've done it. It feels like I'm a little bit tougher than I was. I have more confidence. 

'I got really into these hawthorn hedges in the woods near where I live. The way the branches weave together reminds me of a human brain and I love the way that the rain flows along them and the life that's lived in them - it's like this path you choose to take and it gets thinner at the end. And I used to draw these things endlessly, for weeks on end, I used to go sit in the woods and draw these trees. I still do it.' 

Did your friends stick by you through what sounds like a breakdown of some kind? 

'They were brilliant. Even when I was being a bastard , they were really cool about it. That's when you find out... and that's another cliche. What I should really be doing is wearing a cowboy hat...' 

Do you think the rest of the band is secure with your new recording methods now? You could work alone if you wanted to. 

'No, but you see, I couldn't. Well, what I'd been saying to them all along... I'm built to always work with other people.' 

What do you get from them? 

'Points of reference. Otherwise, I'd just go off in lala land and then I don't know where I am, what I'm doing. It all becomes meaningless. Because I'll get bored or frustrated. My running joke with myself is like being one of those ad executives: you know, the ideas man, the painfully annoying neurotic ones who run around banging loads of charlie and coming up with one idea a month? That sort of thing.' 

Kid A is the one of the first albums to make good use of the CD format. In the days of vinyl, artists were limited to 45 minutes worth of music, split down the middle. CDs have made it possible for records to grow enormously in length, beyond what many of us are prepared or able to take on in a single sitting. As a result, we skip about, consume in byte-size chunks, much as we do in so many other areas of our lives: as the author James Gleick points out in his book Faster: The Acceleration of Just About Everything, we are gradually losing the ability to relax and focus on one thing for any length of time. 

To be appreciated in the initial stages, Kid A demands to be heard continuously, as a piece, in the same way that much classical music does. If this care, or rather desire, is not there on the part of the listener, it gives little of itself away. But under the right circumstances, when it does, it turns out to be the equal and more of its predecessors.

From the opening strains of 'Everything In Its Right Place', with its elliptical piano motif and mantra-like vocal, to the near devotional hush of 'Motion Picture Soundtrack' at the end, this is a record which constantly surprises with its emotional range and beauty. As if to underscore the point, Radiohead are refusing to release any singles from it, or make videos. In future, they say, they may choose to issue material as and when it's ready, over the internet, thus avoiding the bi-annual marketing putsch. 

How do you think Kid A is going to be received? I asked Yorke 

'I think people should just decide for themselves and we'll be getting on with something else. That's about it. No other feelings. If people have a problem with it, well, I wont be reading about it anyway. And I won't be apologising for it. You can't make music and then be responsible for the way that people receive it all the time. [Sarcastically] Not unless you really know your market.' 

Is the title a reference to Carl Steadman's book, Kid A in Alphabet Street? 

'No. It just seemed to work. I think the best ones are usually like that. Often, if you call it something specific, it drives the record in a certain way. I like the non-meaning. All sorts of bizarre things have come up in relation to it. But the one I like is based on the idea that, somewhere, some errant scientist has already created the first completely genetically cloned baba - Kid A. I'm sure its happened. I'm surre somewhere it's already been done, even though it's illegal now.' 

Colin was saying that you and the others all have what he characterised as a middle-class aversion to altercation. 

'Well, I think a lot of that is... I guess in a way... we were all brought up in kind of an... those sort of schools are ultra, ultra competitive. And you never really lose it. Like that bloke in Big Brother - he says, having not watched it.' 

Nasty Nick? 

'I absolutely recognised him. And you look at him and think, "You absolute arsehole." But then you think, "No I was brought up like that." Achievement is everything and if anybody gets in the way you just want to kill. I think there was quite a lot of that and... that was one of the things we had to sort out, really! Cos it couldn't carry on like that... like if you were a businessman and every time you didn't get your own way, you got really vindictive with the people involved, then...' 

You were inclined to do that? 

'Oh yeah. Big time. Because I felt like... it's a weird thing because if you have something in your head and it feels like its going there, then suddenly it's being dragged away by other people, you freak. Because, essentially, in order for me personally to stay OK about what I do I have to see through whatever it is that's appearing in my head. That's my instinct, anyway, but then the best things are often those that go somewhere you weren't expecting. It's learning to trust to that. The whole point of being in a band and having Nigel [Godrich] produce us is that things happen that I don't know anything about. And the best feeling in the world is when you sit there and watch it go somewhere unexpected. 'How to Disappear' on Kid A , for instance, I had no involvement in that at all after the demo stage. Jonny did everything else. We managed to turn it into this incredible thing. I think that was good for me to see that happen and to let it happen.' 

Are you still surprised by what comes out of Radiohead? 

'Oh yeah. That's the qualification for a song that goes on the record. Each one has had that happen to it. That's the best thing in the world. It's why I keep doing it.' 

Spitting Image once did a skit on Orson Welles, under the title of 'The man who lived his life backwards'. Now look at this. What about the band who started out with an understated, little-understood album of opaque but brilliant songs, which John Peel loved, then went on to a critically acclaimed middle period, culminating in the big corporate sell-out and success in America with a compromised album at the end. Now look at that backwards. It's Radiohead, isn't it? What do you say to these people? Except, perhaps, 'this is pretty cool, huh huh huh...'