Smith must have had the Trainman's help.
First, some background:
When Agent Smith was destroyed by Neo at the end of The Matrix, he was flagged for deletion.
You destroyed me, Mister Anderson. Afterward, I knew the rules, I understood what I was supposed to do but I didn't. I couldn't. I was compelled to stay, compelled to disobey. And now here I stand because of you, Mister Anderson, because of you I'm no longer an agent of the system, because of you I've changed - I'm unplugged - a new man, so to speak, like you, apparently free.
What were those rules he was talking about? The Oracle had just previously explained:
The Oracle: ...usually a program chooses exile when it faces deletion.
Neo: And why would a program be deleted?
The Oracle: Maybe it breaks down. Maybe a better program is created to replace it - happens all the time, and when it does, a program can either choose to hide here, or return to The Source.
Since Smith chose to "disobey", he was evidently an exile hiding in the Matrix.
As you know, the Trainman controls Mobil Avenue, which is used by exiles to enter the Matrix. It is also important to note, however, that the Trainman works for the Merovingian -- so, effectively, the Merovingian controls who can enter the Matrix through Mobil Avenue.
In Neo's case, the Merovingian ordered the Trainman to keep Neo in Mobil Avenue because the Merovingian hates the Oracle and therefore opposes Neo (because, as The One, Neo is part of the system devised by the Oracle which rendered the Merovingian obsolete). Preventing Neo from re-entering the Matrix prevents Neo and the Oracle from working together.
However, Smith and the Merovingian have common enemies in the Oracle and Neo (the enemy of my enemy is my friend). The Merovingian undoubtedly ordered the Trainman to help Smith so that Smith could work against Neo and the Oracle. This is probably also how Smith acquired access to the backdoors (see the second point).
It is possible that Smith somehow had access to the Matrix through some other route due to the fact that he was a former Agent. However, the fact that Smith explicitly says he is no longer an agent of the system suggests that this is not the case. Furthermore, the Agents don't seem to have a special route into the Matrix anyway, since Rama Kandra told Neo in Mobil Avenue that
I know that if you want to take something from our world into your world that does not belong there, you must go to the Frenchman.
Rama Kandra told Neo that this was the only way into the Matrix from the machine world, so it doesn't seem that the Agents have another route. Furthermore, as an exile, Smith "does not belong [in the Matrix]" so Smith would have had to go to the Frenchmen (the Merovingian) to re-enter the Matrix.