Shawn was his own worst enemy and the SuperCena like push he received didn't do him any favours.
Let's actually look at why he didn't get over with the crowd as face champion, and he didn't, by looking at his feuds over the title.
vs Bret Hart leading into Wrestlemania 12 - Shawn was booked as the cocky character he always played, a flashy guy who gets the girls and doesn't care what anyone thinks about him. Bret was booked as the hard working, down to earth, underdog that rose to the top and stayed there because he was that good.
No surprises that Bret got more cheers than Shawn around this time, Shawn was basically booked as a character that men couldn't identify with. Bret was almost a forerunner for the Steve Austin character, a working class hero to be proud of. Vince should take most of the blame for that, Shawn should have known that he needed to change his character up.
The promo video says it all:
http://www.youtube.com/watch?v=6sm0f887rLM
vs Diesel for In Your House - First of a pattern to follow whereby Shawn overcomes all odds to somehow take the gold home, something a lot of people hate Cena for today. Anyway Diesel was well on his way to perfecting the Kevin Nash/nWo character that got him massively over. Watch the match and the males in the audience want Diesel to win by the end, especially after Shawn gets beaten up for the entire match and wins with relative ease at the end.
This should have told Vince and Shawn that this stacking the odds for him to overcome wasn't working with winning over the men in the audience, sadly they stuck with through the next feud
http://www.youtube.com/watch?v=5Uwwa6Uj35E
Around this time the obnoxious Kliq Kam started appearing too, that was one of the lamest things a WWF/E champion has ever done and further alienated from anyone that wasn't a kid or that didn't want to have sex with him.
Next proper feud was with Vader. Again a monster heel, who had been crushing all in front of him, but one that Shawn would heroically overcome. The Summerslam match was very poorly booked, in that Shawn looked like he wanted to get the hell out of there like a coward with a count out and DQ loss, before eventually besting Vader. We know now that HBK pulled a creative card, as Vader was originally supposed to win the title here to lose back to HBK at a later date, and even before the IWC existed it was obvious to a lot in the crowd that that should have happened, given the way the feud was booked. It made no sense to blow off Vader like this, he was getting very over as a heel, but HBK decided he didn't want to work with him and that was that.
A great match, but a throwaway feud followed with Mankind. Vince should have steppe din here and realised that Foley had the tools to get HBK over with the section of the crowd he couldn't, but didn't pull the trigger on a proper run here. The nWo were up and running by now, which didn't help the Kliq Kam's coolness one bit.
On to Psycho Sid. Yet another monster for HBK to go over, although this time they had a twist in the tale. All reports indicate that HBK was supposed to hold the belt til Wrestlemania 13 to drop to Bret, but HBK and Vince wisely decided that dropping the title to Sid, so that he could win it back in his hometown of San Antonio, might get him some of the face champion heat he was lacking.
At the Survivor Series though the New York crowd were so behind Sid that it made HBK look very, very bad. This is the match where HBK really lost his cool with the audience and goes pretty mental at them. hell the audience even cheered Lothario getting knocked out by Sid, such was their hatred for HBK.
Also watch the ending after Sid has won, way to sell the powerbomb and camera shot Shawn
http://www.youtube.com/watch?v=Fhv6Siz5Wi8
So Shawn wins it back in his hometown, but we all know what happened then with the fake knee injury. That killed Shawn as a face, Bret even called him out live on Raw for faking the injury, confirming in most people's eyes what they suspected.
So who to blame?
Vince and Shawn are much more to blame than the nWo for Shawn's awful 1996 run. They should have realised after the Diesel match that they needed to change his character slightly, they should definitely have known after the Mankind match that HBK needed a wrinkle in his lame fan favourite gimmick. He was SuperCena x1000 and the male audience pretty much hated him for it. The nWo didn't come into play until after the Vader match, keep that in mind, by that stage he was being booed out of the building pretty regularly