I've found that a fun deck is usually one which uses an unorthodox Pokemon combination or strategy to win. Not that all decks that have that particular combination are fun. One I made back around when Neo Destiny came out, with Cleffa and Unowns as the only Pokemon... it won a lot. In Unlimited, it could go up against even Chansey decks just fine. But it wasn't much fun taking 5 minute turns, which was about the average turn length at normal playing speed. Its only saving grace was that playing a winning deck that had barely-used cards like Blaine's Quiz #3, Revive, and Here Comes Team Rocket! in it as parts of the core strategy was kind of fun.
My most recent Unlimited deck, with Mr. Mime and Lt. Surge's Raticate... that's an example of a fun, unorthodox deck that was good enough to challenge at most tournaments I played in.
More recently, I've had a lot of fun with my Ho-oh ex deck because it's got a few "surprises up its sleeve" but it isn't too time-consuming to think of what to do in a particular situation, unlike my old Unown deck. I imagine Golem or Whiscash decks are fun, because of the unorthodox way you can force your opponent to think about whether it's good to attack or not.
Another thing... I think a deck isn't fun if it can't put up a good showing against competitive decks. It isn't fun to be blown out consistantly. But it also isn't fun to consistantly blow out other people in the traditional way, overpowering them with the same strategy over and over. Basically, I find that fun decks are decks that allow BOTH players to have fun.