Time travel is possible in Futurama, and this makes for some rather complicated situations, that I'll try and explain here.

Roswell That Ends Well:

In this episode we find out that Fry is his own grandfather. This may seem like a paradox, but it is actually fairly easy to explain. Fry didn't go back in time and become his own grandfather, he always was his own grandfather. He has always lacked the delta brain wave due to this, which protected him from the brains in The Day the Earth Stood Stupid. This was true before he even froze himself. The Roswell conspiracy theory and the Loch Ness monster picture are also 'explained'. In 1947, Fry, having travelled back in time, slept with Mildred. Then, in 1999, Fry got frozen, arrived in the year 3000 and ended up going back in time. He thought Enis was his grandfather because that's what Mildred told everyone.

In Anathology of Interest I, Fry asks what would happen if he had never come to the future. Unlike the other 'What if?' questions, this causes the universe to be destroyed, as Fry never froze himself and went back in time and therefore was never born. This caused a rip in the space/time continuum.

The Why of Fry:

In this episode, Fry finds out about why he was frozen and is sent on a mission to stop the brains from destroying the universe, and ends up going back in time to the night he was frozen. This bit is much more confusing and complicated. Here is a timeline:

December 31, 1999:
Version 1 - Nibbler makes a call as I.C Weiner and gets Fry to the cryogenics building. He blows Fry's chair and puts him into the chamber.
Version 2 - A time-travelling Fry catches Nibbler just about to put old him into the chamber. Nibbler gives him a choice: either keep his 20th century life, or save Leela and the universe. Fry blows himself into the tube, and disappears after telling Nibbler that 'Scooty Puff Jr.' sucks...

Circa April 3003:
Version 1 - Fry goes into the brains' database on his Scooty Puff Jr. It breaks, and he is sucked into an alternate dimension, where he goes back in time to the year 1999.
Version 2 - Fry escapes the brains' database on his Scooty Puff Sr.

As far as I can see, this is a paradox: Fry goes back in time and changed the future in such a way that he does not travel back in time. I can't see how two different versions of the same moment in time can be shown, unless we're talking about alternate realities, which I don't think we are. The show seems to have changed its stance on the way time travel works from 'Roswell That Ends Well'. I think this is the time to realise that it's just a TV show. I know very little about Physics, though, so if you can explain this, please email me.

Professor Farnsworth: Choke on that, causality!