People who've said "no" to Al

[JEDM]

Lady Gaga's manager
The song: Born This Way
The long version: "The Gaga Saga", and the "Gaga Update!"
The short version: Her manager lied, and she hadn't even heard the song until Al put it on Youtube. She gave her full blessing, and it will appear on Al's 13th album, "Alpocalypse".

Michael Jackson
The song: Black or White
The story: After "UHF", Al was looking for the next big thing to parody for his next album, and once again, he approached Michael about a potential parody. Michael declinded since "Black or White" was a "message" song.

Thankfully, that little band from Seattle came along...

Paul McCartney
The song: Live & Let Die
The story: Al was looking to parody Paul's cover of "Live & Let Die" into "Chicken Pot Pie", but Paul declined since Paul is a vegetarian. Paul & Al still seem to keep in touch since Paul appears in "Al's Brain".

Daniel Powter
The song: Bad Day
The story: Al approached Daniel about doing a parody of "Bad Day", and Daniel declined. Powter contacted Al the day before we went back into the studio to record "White & Nerdy", and Al reportedly told him "that ship had sailed."

Prince
Led Zeppelin

Atlantic Records
The artist: James Blunt
The song: You're Beautiful
The story: Al sought and received James Blunt's full permission to parody "You're Beautiful", but Atlantic Records, James' label, thought it wasn't the right time for Al to parody him.

Any additions & corrections are highly appreciated.

[Big Spoon]

Slight correction, Powter contacted Al the day before he went back into the studio to record W&N, not while he was in the studio.

[Way_Moby]

Yoko Ono told Al he couldn't parody "Free As a Bird."
Rivers Cuomo (of Weezer fame) asked for Al to take out the "Buddy Holly" section of "The Alternative Polka."
U2 approved a parody of "Numb" called "Green Eggs and Ham" but the Dr. Seuss estate refused to license the lyrics off.
Al was going to release a parody of "I'll Be There For You" (Theme from 'Friends') but the shows producers didn't want the song to be over-exposed.

[Marko_The_Odd]

Didn't the Offspring deny Al permission to do Laundry Day?

[OneWAY]

Yeah, I believe the quote was "They thought it was too silly."

[Yankomaniac]

Hah, maybe if they hadn't denied him, we wouldn't have Pretty Fly For A Rabbi. Wish he could have used "Moldy Now" on an album, that parody was hilarious!

[Orthography Enthusiast]

At least Led Zeppelin let Al cover that chunk of "Black Dog" for "Trapped In The Drive Thru" thereby proving they are Good Sports after all.

[Yankomaniac]

Good call, that could be a Page and Plant type thing. Page may be more willing with the music, well nowadays at least, Plant is pretty potective over his lyrics, they are quite legendary!

[mrmeadows]

Yeah, I believe the quote was "They thought it was too silly."

And "Pretty Fly for a White Guy" wasn't silly?

That's too bad. I think I would have preferred a parody of "Come Out and Play", and always thought the "Laundry Day" idea was clever ("You gotta keep them separated", as in whites and colors...ha!) And, as implied above, the original "Pretty Fly" was already a funny song, so it was a bit redundant. Not to say "Rabbi" isn't cool...I like it fine.

[TMBJon]

I'll be honest, I'm glad we got Pretty Fly For A Rabbi out of it because it's one of my favorite Weird Al songs. Laundry Day is a good concert only song, but it probably wouldn't have been funny if stretched out to full length.
FWIW I think I remember reading on alt.music.weird-al that the Offspring had turned Al down because Come Out And Play had a serious message. Sort of the Black & White, Live & Let Die, and Born This Way thing...