At the beginning we aren't aware of it, but this film also undermines itself, becoming impossible in an effort to explain itself.  But let us not begin there; we will begin in the future, three years after Rufus made his fateful trip to 1988 to help Bill & Ted, in 2691.

We are introduced to De Nomolos, an impressively threatening villain within the comic setting played by British actor Joss Ackland.  (He has appeared in quite a few of the British television exports, including the Sherlock Holmes mystery The Copper Beeches, but will be best known to American audiences for his turn as the South African diplomat in Lethal Weapon 2.)  De Nomolos despises the relaxed freedom of the future, and wishes to impose order on the chaos.  His plan:  destroy Bill & Ted before they can become the famous band Wyld Stallyns, and so undermine all of history.

You already see the problem.  As has been said innumerable times on this web site, any effort to intentionally alter history will either fail or create an infinity loop.  If De Nomolos succeeds, he will have undone seven hundred years of history so completely that the probability of his own existence in the altered timeline is statistically insignificant.  (At roughly four generations per hundred years, twenty-eight generations have passed.  The life or death of even one individual in the first generation could so alter future progeny as to completely change most of the world's population in that time, and the changes made by Bill & Ted are expected to change the entire world drastically in that generation.)  Even if his success is not his undoing, he will have erased the reason for his actions and so will not make them.  Fortunately, he fails; how he fails becomes the story.  He begins by capturing a time machine and using it to transport his humanoid replicants, known as the Evil Bill and Ted robots, back to 1991 to prevent the boys from making their earth-shaking appearance at the Battle of the Bands concert in San Dimas.

Rufus manages to catch on to the time machine as it is leaving 2691; however, he does not appear with it in 1991.  We later learn that he was thrown back in time further, although the temporal distance is not clear.  This is important to the time travel situation in multiple ways which will be addressed later; but their are a few points to be made here.  First, as we noted in connection with Star Trek:  First Contact, Rufus' departure from the future is part of the same time travel event and so does not create a separate anomaly.  It is more complex this time, but the same in principle:  time stops at the point when the robots and Rufus leave 2691, and snaps back to the moment Rufus enters history.  It then progresses to the point when the robots enter history, but as they are part of the same departure they are also part of the same anomaly.  This avoids the classic problem of the second time traveler leaving after the first to fix that which was changed (the Time Cop problem, in which the moment at which the second traveler departs can never exist unless the first traveler failed to make the changes).  Between the arrival of Rufus and that of the robots, a critical story element occurs:  Wyld Stallyns is entered as the last band in the San Dimas Battle of the Bands.  A Mrs. Wardro is supervising this, and puts them at the end of the night, making excuses for including them.

At this point we are confronted with a new question about time.  Evil Bill & Ted contact the future and speak to De Nomolos.  The problem is not that they call him, but that he answers.  Each time he replies, a new anomaly is formed.  Observe it carefully:  Evil Bill and Ted contact him, but in doing so they have altered the past, because they were not there to make that call in the previous timeline.  Therefore seven hundred years must elapse before the De Nomolos who receives that call can exist.  Their method of communicating to him is in principle not any quicker than placing an ad in The Washington Post and waiting for him to read it.  Only after he has heard the transmission can he respond; but his response changes history, because it could not have reached the past in the timeline in which the robots first made the call.  Thus each time he answers them he creates a different seven hundred year history.

The temporal communications create another problem for us as well.  The moment the robots travel into history, De Nomolos must know that they have failed.  Every event which springs from their arrival in the past will have happened by the time he receives the first message.  If history has not been altered, he knows he has failed.

But the transmissions are more for story color than for plot.  They don't matter.  They succeed in keeping De Nomolos before us as a continuing threat behind the scenes.  The robots have been programmed, they know what to do, and they do not need additional instruction to fulfill their mission.  Thus we can ignore these transmissions from the future.

The robots kill Bill and Ted and begin to destroy their lives.  They again contact the future, which again is not important (but it does create another set of anomalies).  The boys face hell, defeat death (incidentally proving themselves masters of playing games), pick up a brilliant alien scientist (named Station) from heaven, and return to life (with death and the alien).  Again the robots contact the future, with the same results.

The alien scientist builds a pair of Good Bill and Ted robots who look terrible--until we realize that they aren't intended to be Bill and Ted, but to be Bill and Ted's alter-ego Rock'em Sock'em robots--another game (although I'm not sure how many younger viewers would recognize them).  Confronting their evil robot duplicates on stage at the Battle of the Bands, they use the Rock'em Sock'em robots to knock the heads off the evil twins and smash their internal controls.

We must diverge from the script at this point and consider the timeline.  No matter when De Nomolos realizes his robots have failed, he cannot make a trip back to this point in time until the rest of history has played itself out and stabilized.  Each of his transmissions to the past have set up a new repetition of history, each leading to these same events.  But he cannot in this timeline appear on the stage.  Therefore Bill S. Preston, Esquire, and Ted Theodore Logan must begin their concert.  They can make their speech about the places and times they've visited, and how wonderful it is to be here, but frankly their music is terrible.  Still, they have put on a fabulous show and played on Channel 12 in San Dimas, so they might win the contest on showmanship alone (very important in the popular music world--after all, even the Beatles used studio musicians on their albums).  They could very well create the future with which they are credited, although it will be a much slower process.  They do have the assistance of Death and the scientist Station to help with future shows, and the Rock'em Sock'em robots are still intact.  They can work up a good show.

But we are forced to look a step back and ask what would have happened had Evil Bill & Ted never arrived.  Sadly, the movie fails on this point, because they would have had no show, no message, no glory, and no future of peace and brotherhood which De Nomolos would wish to destroy.  However, this particular history--the one in which Bill and Ted appear at the Battle of the Bands but Evil Bill and Ted did not arrive to interfere--never happened.  But the reason for that has not yet been revealed.

As time reaches 2691, De Nomolos realizes that he has failed, and somehow steals a time machine to go back and do it himself.  Again, he faces the same hazards he created by sending back his robots, but he has not considered these.  De Nomolos then in large part intensifies the history he wishes to avoid:  He gives his enemies a world-wide audience they could not have had without him.

What happens in this timeline is highly speculative.  Bill and Ted decide to set up the sandbag, but it is not there.  In a bloody shoot-out, the police capture De Nomolos, but the boys escape.  At this point it might not matter whether or not they perform, because they have a time machine on stage, and they know how to use it.  Once De Nomolos is taken, they take the time machine, and quietly go back to set up the sandbag.  Note that if De Nomolos is not captured or killed, they cannot make the trip in his time machine, so they have to win; but as we discussed in Terminator, if something bad hasn't happened they will have no reason to do so.  Thus I suggest that De Nomolos hurt, possibly killed, some people other than the boys, leading them to decide to undo it.

This sets up another timeline, because on cue the sandbag falls, smashing the gun in De Nomolos' hand.  But the villain is infuriated, and Bill and Ted suddenly realize they should have included a cage.  He charges them, and is again taken prisoner.  Again Bill and Ted use the time machine on schedule, this time installing the sandbag and the cage.  De Nomolos is captured in the new timeline.

He suggests that he, too, can travel back and make changes.  He produces a key for the cage.  He then produces a second gun.  But Ted tells him that he's mistaken:  only the winner can go back and make changes.  This point is critical to our understanding of time travel:  in order to make the trip back to fix the past, you must have survived to make the trip.  Bill and Ted take credit for the key and the gun.  But this means two more trips.  First they must plant the key.  This strikes me as unlikely in the extreme.  De Nomolos appears to draw it from his pocket, which would mean they would have to have found him before he appeared on stage and planted it in his pocket; but he just came from the future, a time and place unknown to them, so it would not be easy to do.  But overlooking this logistical complication, they must have decided that it would make for a better show if they also provided him with a key.  He pops out and announces that he has arranged for another gun, but it isn't there, so he is taken by the police.  Again Bill and Ted go for the showmanship, and in this timeline add the gun, the fake gun which promotes them.  Finally De Nomolos is taken into custody, no one is hurt, and the show is perfect.

In each of these timelines the next event is that Bill and Ted are faced with the fact that they are lousy musicians asked to perform to the world.  The world has seen only the tail end of this show, but could still be impressed.  And these concerts don't matter too much, because in each case the boys are about to go back and make changes to history, so they'll get another first try.

And they still have the time machine, and they still know that this is a critically important moment in their lives.  So having bombed at the concert, they now abscond with the time machine, make that trip back to alter the past, and then begin their intensive training in how to play the guitar.  Oops--they create another anomaly, a complex N-jump in which most of the events of the film (those occurring in the twentieth century) are repeated precisely, when they take a time trip for a two-week honeymoon back in the fifteenth century.  Sixteen months in the future, they change history by going back to the stage and taking over the concert.  Note that this will be a self-sustaining loop.  Bill and Ted will now go into their intensive guitar training and come back in sixteen months, and since they will have made this change before the time machine was sent back from the future it will be part of the history remembered in the overarching anomaly.

And finally we discover what became of Rufus.  As we indicated, he was thrown back some time before the audition.  Finding himself in this time, he replaced Mrs. Wardro and took over supervising the Battle of the Bands concert so that Bill and Ted would have the right place in the show.  And this leads to the final disastrous anomaly.  We are forced to try to determine what would have happened to Wyld Stallyns without Rufus' intervention.  The answer, I fear, is worse than the first film:  they would not have participated in the Battle of the Bands, and so never would have achieved fame or changed the world.  In fact, we are pressed to conclude that everything Wyld Stallyns became was due to De Nomolus' efforts to destroy them.

And on this one point hinges the history of the first film as well.  Without Rufus to intervene and include them in this concert, the successful history report no longer matters; they remain unknown musicians, and no one will be sent back to assure their success (or even know that history was changed).  The initial non-appearance of Rufus as Mrs. Wardro will undo everything, and Bill and Ted will never have mattered.  The unknown traveler (the other Rufus) who helped the boys with their report thinking it wouldn't make any difference to history was right, and the original future is confirmed in an N-jump in which the utopia Rufus seeks to preserve and De Nomolos to destroy has never existed in any timeline.

I fear that Bill & Ted's Bogus Journey has repercussed to make their excellent adventure just as bogus.