This might seem ridiculous, but I realised that, years after I watched the film, I've still no idea to whom the title was referring. Who was it?
Seriously - who was "The Phantom Menace"?
Simple Version: The actual phantom menace was the one Palpatine/Sidious created merely for the sake of taking over the Senate.
The point, and using the name The Phantom Menace just emphasizes it, is that the threat to Naboo may be real, but it's secondary to Palpatine's real goal, which is to make Naboo feel threatened (or menaced) so it was easy for Palpatine to manipulate the Senate into doing what he wanted.
More In Depth Version: Since Palpatine controlled the Separatists (I'm including the Trade Federation with them) through Dooku (without anyone knowing it), he was able to order a blockade around Naboo. Since it was his own homeworld, that would also help with appearances when he showed any extra concern to help break the blockade.
His whole goal was for Amidala to plead in front of the Senate and for there to be enough sympathy for her cause (and him being from that same planet gave him sympathy points, as well) that when she asked for help and Chancellor Velorum was able to only give her standard rhetoric, Senators would be behind her when she moved for a vote of no confidence.
His entire goal was to put Amidala in such a vulnerable position that people would support her when she asked for a vote of no confidence. Then, once that happened, it would be easy for him to manipulate the sympathy and concern into votes to elect himself as Chancelor.
While he was interested in Naboo, that was not nearly as important as becoming the Chancellor, which would put him in a position to eventually take control of the Senate. Even though Palpatine had other plans for Naboo, what mattered most was the issue in the Senate.
There's a subtle shift of focus (that is, literal camera focus) at the end of the movie that illustrates who the Phantom Menace is. It comes soon after Yoda's line:
Always two, there are. No more, no less. A master... and an apprentice.
Shortly after this line, the camera refocuses onto the Phantom Menace, revealed to be:
Palpatine
According to George Lucas in "The Force Is Back" (by David Kamp, Vanity Fair, February 1999):
Given that The Phantom Menace is a Vader- and Emperor-free movie, the role of evil string-puller falls to someone we’ve never heard of. “The phantom menace is a character named Darth Sidious,” Lucas says, “who is the last of the Sith” (“An ancient people . . . conquered by powerful dark-side Jedi magic”—page 268, Star Wars Encyclopedia, by Stephen J. Sansweet). Actually, Lucas goes on to explain, the “menace” honorific should be broadened to include Sidious’s apprentice, Darth Maul, a terrifyingly fierce-looking character played by the martial-arts expert Ray Park.
The Phantom Menace was the Sith Master the Jedi council realized must be behind the scenes, pulling the strings:
Yoda: Always two there are, no more, no less. A master and an apprentice.
Mace Windu: But which was destroyed, the master or the apprentice?
Wikipedia confirms the Palpatine theory that others have mentioned in their answers:
While the working title for the film was The Beginning, Lucas later revealed the true title to be The Phantom Menace; a reference to Palpatine hiding his true identity as an evil Sith Lord behind the facade of a well-intentioned public servant.
According to the official Star Wars databank, it's Palpatine.
From his character bio [emphasis mine]:
Scheming, powerful, and evil to the core, Darth Sidious restored the Sith and destroyed the Jedi Order. Living a double life, Sidious was in fact Palpatine, a Naboo Senator and phantom menace. He slowly manipulated the political system of the Galactic Republic until he was named Supreme Chancellor -- and eventually Emperor -- ruling the galaxy through fear and tyranny.
A phantom menace also means an unknown evil. In the film, two major unknown evils include:
1) Senator Palpatine hiding his Sith Lord and (later) Galactic Emperor persona and
2) young Anakin (later to become Darth Vader).
Darth Maul could even be considered a phantom menace because no one knows who he is and where he came from. In my opinion however, I believe that the "real" phantom menace (title of the film is 'The' Phantom Menace, therefore there is only one) is Anakin Skywalker. The point of the two trilogies was to tell the story of Anakin's life and death. It makes sense for the first episode in the series to retroactively introduce the young Anakin while the audience was fully aware of his (evil) future.
The Phantom Menace is not a person, but a reference to the overall situation that the characters find themselves in throughout the movie.
Though we have several villains in the movie:
Menace is defined simply as
a person or thing that is likely to cause harm; a threat or danger.
Sometime during the film, but off-screen, the Clone Army is ordered:
OBI-WAN: Yes, Master. They say Master Sifo-Dyas placed the order for a clone army at the request of the Senate almost ten years ago. I was under the impression he was killed before that. Did the Council ever authorize the creation of a clone army?
MACE WINDU: No. Whoever placed that order did not have the authorization of the Jedi Council.
This answer, talking about Episode II
We know that this was done so that the Empire would have an army to use later. The use of this army must be justified, though, as it has been a long time since the Republic had a standing army. As such, the Sith must create an environment in which no one will even blink when they destroy the Republic in favor of the Empire, and adopt this army.
How does one precipitate the chain of events that need to take place to see the rise of Palpatine and the Empire? By creating fear and confusion, and manipulating those most affected by said fear and confusion into pushing events forward.
This is largely accomplished with the blockade of Naboo. This directly results in Palpatine becoming the Supreme Chancellor, as Queen Amadalla herself calls for a vote of No Confidence in the current Chancellor, an action for which Palpatine is already prepared with votes to gain the position.
Even though the main villain is definitely Palpatine, we can safely assume that The Phantom Menace is simply the menace of the situation, the origins of which are hidden from the Jedi and the Senate, as well as the galaxy at large.
Maybe I have a weird view of things, but I always saw the The Phantom Menace not as a person, but as a concept in general.
Think about what Darth Sidious' plan was all along, he wanted to rule the galaxy. The way he devised to do that, was to convince the republic to vote him chancellor and to vote to give him "emergency powers".
The way he chose to do this, was to make the republic feel like it was threatened, so that it would be forced to accept the clone army(which later become the main soldiers for the empire) and by voting for a chancellor and giving him powers they thought were needed in order to defend the galaxy.
Remembering a definition of Phantom:
a figment of the imagination.
And the defintion of Menace:
a person or thing that is likely to cause harm; a threat or danger.
Sidious created a fake threat, the separtists and their rebellion, to make the republic think they were being threatened so that they would do what he wanted, put him in power.
So The Phantom Menace is in fact, the false threat Sidious invented to manipulate the senate and the republic.
I always thought it referred to Darth Maul, but I may be wrong. However, I have not been convinced otherwise as of yet. Darth Maul was stalking Qui-Gon and the others on Tatooine like a phantom, with his Sith macrobinoculars, probe droids and what not. He certainly proved to be a menace when he stabbed Qui-Gon with a [badass] double-bladed Sith lightsaber.
