I haven't done the update yet but I ran across this article. Hope you read this before you go through a full clean install which I know is a huge consumer of time. Looks like updating something in Java fixes it..... at least for CS5... which is the version of Creative Suite I own right now.
I'm assuming you're talking about the actual Adobe software and not just the player. Might be helpful to know what version of Flash you're running as well. Just for the record if someone comes back to this.
Since OP mentioned going to vevo.com, it's more likely they just meant the player. My issue was with the player as well. The latest version of Flash would appear to install but websites were not recognizing it.
For the record, a reboot seems to have fixed it in my case.