Watchmen is the first movie I've seen that is based on a comic book, but is not a comic book movie.
Certainly, the characters wear costumes and do outrageous things; one of them even has superhuman powers. However, the movie is not about men in tights beating up other men wearing capes (... although we are reminded as to where Edna Mode of The Incredibles got her "No Capes!" mandate ... poor Dollar Bill! ...)
Think about how the Incredibles (which was not originally a comic) was basically about a nuclear family (in the non-super-powered sense) dealing with transitioning from a pair of freewheeling newlyweds to responsible parents with appropriately bratty (that is to say: healthy!) kids. There, the superhero motif works (where the Spiderman movies are mere fluff) because the Story is more important than the Spandex.
Likewise, Watchmen is not about how Ozymandias got to be the World's Smartest Man or where Nite Owl II build his Nerdship or whether The Comedian can beat the crap out of Moloch once again. The core of Watchmen could have been made without any costumes at all; put everybody in a suit, make Dr. Manhattan a brilliant physicist, and what changes except for the gratuitous (...although visually nice...) sidetrip to Mars? This would still be a finely plotted action/adventure thriller, built around a murder mystery that leads to a Vast Conspiracy, with a dangerous love triangle for spice. It just wouldn't be as much costumed fun.
The movie tries rather leadenly to Address a Big Question: will we do evil to accomplish good? How many people are we willing to slaughter to save the world from communism, Al Qaeda, or whatever evil is at the top of our color-coded charts today?
We can appreciate the author's intent to be serious while disposing of his solution by rejecting its factual premises. The central characters draw faulty conclusions from a faulty understanding of human nature; it's simply false that we are damned by nature to the Hobbesian brutal world inhabited by the movie's Flawed (to say the least) Heroes (some of whom are honest enough to admit that they are All Barking Mad).
Surely with both a demigod and The World's Smartest Man on the job, they could come up with a better solution than Yet Another Atrocity; we do that all the time in The Real World. And let us not forget that the Flawed Solution is itself unstable, as exposed in the brilliantly-imaged coda.
But the prosaic reality wouldn't give us this Epic Tale of Flawed Heroes, so I'm not complaining.
This may be what baffled the critics: this isn't a comic book movie. It's a movie done in comic book costumes. Think about how "The Magnificent Seven" is basically "The Seven Samurai" in different costume; there is an uber-movie underlying both, consisting ( in the language of web pages ) of the same content given instantiation with different style sheets. (I can't wait to see Seven Samurai expressed as XML and given Mario style ... but I digress.)
One point that distinguishes Watchmen from conventional comic book movies the fight scenes. In comic book movies, they're there for fun and mayhem and setting up the video game & action figure tie-ins. The good guy stomps on some Evil Red Shirts and gets clobbered by a Boss until, in a Climactic Battle, he Discovers Something Inside and fells the Big Bad. In Watchmen, this doesn't happen; the fight scenes advance characterization and plot. For example, the fight in the alley establishes the young Spencer Tracy and Katherine Hepburn characters are co-workers in denial about their mutual attraction. Later, the fight in the prison alley is the Perfect Ending to the Perfect First Date (complete with the annoying friend who has to delay everything to visit the men's room.) This all makes the fight scenes vastly more interesting than the usual pointless thud and blunder.
People who've read the Graphic Novel will notice a few changes, nearly all to the good. Minor roles are combined (no more feckless Captain Metropolis, or whatever his name was) and the climactic Big Thing is vastly improved by eliminating a silly complication in favor of a more logical construction that explains even more of the side events. You'll know what I mean when you see it. An underappreciated addition deals with the graphic novel's lack of emotional resolution to the Grand Climax: somebody deserves punishment, and knows it; in the Graphic Novel it doesn't happen. In the movie, the Reasonable Man does what has to be done and the Guilty Man accepts it. Justice is served, although not even the Cosmic Watchmaker can repair everything.
(I do think the added line "The TV said you were on Mars" is worse than useless; like the "Is that artillery or my heart beating?" line in Casablanca, silence is better than a clumsy line.)
Some critics have complained that the film is too complicated or doesn't explain things well enough. That may or may not be so; I'd welcome comments from someone who hasn't read the graphic novel. However, I did not find scenes that dragged on; perhaps those critics were expecting a simple comic book movie and didn't bring their brains to the party.
This is a mature movie. You can watch it for the action, or you can watch it for the plot; either way, I recommend that you watch Watchmen.