No, "starting with" does not imply future tense. For example,
Starting in February 1999 we began using large pages
describes an action that occurred in the past.
The phrase does imply that some relative sequencing order exists in whatever is referred to. In your examples, where January, 2011 is a date in the past, you might less clumsily write either of
Since January, 2011, we have been using public transportation
In January, 2011, we began using public transportation
Regarding awkwardness of, for example, "Starting with January 2012, the platform will use a two-digit numbering scheme": The problem with this stems, I think, from the first phrase acting like a dangling participle. To avoid the problem, one can move the phrase to the end, or use other wordings:
The platform will use a two-digit numbering scheme starting in January 2012.
The platform will use a two-digit numbering scheme from January 2012 forward.
Beginning January 2012, the platform will use a two-digit numbering scheme.