I have the Utica-Buffalo license quest, which says I need to get 170 bucks (I did), and then I need to ARRIVE IN UTICA to give Jeremiah the money for the license.

One small problem: I don't have a license to open the train to Utica, and if I don't have that I can never arrive in Utica to complete the deal.

Is this bugged, or am I overlooking something essential?

You need the bit from Boston - Utica for that. If you lie about your name during the first quest you get a little extra quest incl. the license for Boston - Utica, otherwise I think you have to buy it.