Calling them "royalists" is a bit of a stretch--it would probably be more accurate to call the Vendémiaire rebels Anti-Convention rather than Anti-Republic. There were a slew of radical republicans and moderate constitutional monarchists alongside the royalists in those crowds, although the royalists certainly made up the vast majority.

Bit of background: the Convention, especially after Robespierre, was seen as a very ineffective government. The reaction after Robespierre's execution was very strong, and radical republicans (IE the Jacobins) became targets of execution and mob violence just as royalists had been during the Terror. This created a political situation where most of the assembly were either exceedingly moderate republicans, or had some sort of monarchic tendencies, whether they were constitutional monarchists or full-blown royalists.

This, as one might expect, created gridlock. Most of the assembly was at least sympathetic to monarchy, even if they didn't want to see its return, and post-Terror the mood had swung decidedly to the conservative. Unlike in the early days of the republic, sweeping reforms were no longer being made--indeed, some reforms were being rolled back.

The Convention had its hands tied, however, because the army was still hyper-liberal. If the Convention moved too far to the right, especially if they made any pro-monarchy moves, there was a formal understanding that the army would depose the Convention (or whatever government they tried to usher in) to restore the Republic. So the Convention couldn't move too far or too fast to the Right, and were unwilling to make many concessions to the same Left which had spawned Robespierre--effectively, no route but the status quo was available to them.

So, although the government still had plenty on its plate between France's wars and a rapidly deteriorating economic situation, the people weren't seeing it do very much. In fact, the common people were already furious with the government, because price controls on grain and other foodstuffs had failed after two successively poor harvests.

So gridlock in the government was caused by the anti-Jacobin reaction and the threats of the army. This gridlock combined with reform rollbacks to create a sense that the government was incompetent. This was an already-precarious situation, which was only exacerbated by the economic downturn of '94-'95 and the faltering of the price controls. When the price controls collapsed, the people of Paris blamed the government, and that was the seed of Vendémiaire.

In effect, the rebellion started in the capital itself; there was no need to march to Paris, because Paris was "ground zero," so-to-speak. The anger against the government was felt on all strata of society, from the very top (the exiled and imperiled Jacobins) to the very bottom (peasants and workmen who couldn't afford food). Royalists certainly took advantage of the anger and (largely successfully) attempted to turn Vendémiaire into a pro-monarchic counter-revolution, but not everybody marching in the crowd were royalists, or even cared. Some just wanted bread, or a competent government, or an end to war, and were willing to bring the King back (or at least risk the possibility that the uprising would result in the return of the monarchy) in return for stability.

Sources:

Steven Englund, Napoleon: A Political Life

Rafe Blaufarb, Napoleon: Symbol for an Age: A Brief History with Documents