Hmm, yeah sounds like something funny is going on with your duemilanove.
Does the 'old' DS1307 code work (where it sets the time with the sketch)?
Use that sketch to set the time, then load up the other sketch and see if it has kept the time you set.