Image is everything and unfortunately for the shark, what it does is never going to beat what a cetacean (which is usually see as friendly and at worst benign). The most popular image of sharks for the lay person is that one line of music by John Williams. Image portrayal does help the fight to save a species. For example, the lion is one of the most ferocious killers on the planet... yet we find ourselves thinking they are pussy cats due to movies like Born Free, Lion King and of course the circus acts.
The shark is the top predator in the oceanic food chain. Jaws and media hype following it has damaged its image in the mainstream. Look at the modern movies with sharks in them, they are still super killers (but that's because they ARE). The image of sharks is danger and that's not going to change, because sharks are not cuddly, aren't seen nursing their young (which always get points) and no one really knows a lot about them. So public portrayal is important, but the problem of portraying something that lacks "cuddly" factor means you go back to the visceral side of shark behavior, which partially perpetuates the mainstream image.
The biggest issue is that the main consumers are in Asia (particularly the Chinese, Thai and Japanese) although the super rich Arabs are now on the bandwagon. So we can have all the smiley friendly shark images we want but if it's seen merely as a commodity in asia, then really it's a feel-good measure.
As John Bantin says, softening demand is only way to save them in the long run. That is probably not going to happen and definitely not in time to save most of the sharks species. What is needed is legislation from the likes of CITES and IUCN which will force various countries to comply.
Another issue is the business aspect of sharks fin. Do you think that shark fin suppliers don't know that supply is finite? It's a million dollar industry and triads are involved. These suppliers are using the same endangered species panic to drive prices up, all while sitting on their warehouses of fin like the diamond merchants of Africa. They would love for legislation to force the market to the underground where prices are even higher. But at least then it's out of the mainstream.
As for celebs, I believe Jackie Chan only promoted the preservation of tigers. The restaurants he purportedly has shares in still serve sharks fin. Only the Yao and director Ang Li has publicly denounced sharks fin.
What Stu has suggested is precisely the problem. "Buddha jump over the wall" was originally a fujienese dish that had dog and other land animal meats. It has since evolved into a dish for the affluent to consume and in many restaurants they even throw in sharks fin because it's an expensive ingredient. Shark fin is bling.