Well, according to what I've read, it was Gaga's manager who refused him, not Gaga herself, prior to even letting her hear the song, but after she heard it on YouTube she gave him the go-ahead. I'm not sure how true that is, but I do remember seeing her on some channel talking about what a huge Weird Al fan she is years ago, so I doubt she'd flat out tell him he couldn't parody one of her songs.

As far as the parody goes, he's done much better but its alright. It's certainly no "White and Nerdy".