James Blunt was fine with it, but his record company wasn't. They were concered that a parody of You're Beautiful would just lend to the impression that Blunt was a one-hit wonder.
As far as I'm aware, Prince is the only one who's actually refused outright. Al sought permission before doing Amish Paradise, and got consent from Coolio's company, mistakenly believing it came from Coolio personally.