I liked the time traveling part more than the romance part. Spoilers to follow.
Time travel is a good tool for meditating on the nature of fate in science fiction, much in the same way prophecy was used in classical literature: The paradox of Henry and Clare's relationship is that you can't determine whether it began when Clare first approaches Henry in the library, saying she's known him all her life; or whether it began when Henry first visited Clare as a little girl, having already married Clare in the future. Stated as an intellectual puzzle, it's fascinating (I liked this article on the physics of The Time Traveler's Wife, for example), but to make it into a great story, you need, as always, good characters. Unfortunately, Henry and Clare in the movie come off as rather dull and not fully-formed. I understand, however, that the book presents them in much richer detail.