Here is my reasoning.
最初 refers to the beginning of a time period or to the beginning of a series of events. (Cf. 日本に来たばかりのとき...)
As istrasci pointed out in his answer, the additional に strengthens the time reference. (Cf. 日曜日街に行く vs. 日曜日に街に行く.)
初めて is used, as far as I can tell exclusively, for things you do for the first time. (Cf. 初めて見た.)
The difference between
is maybe best reflected in English as
When I went to Japan for the first time, [the first thing I did was to find a convenience store and eat natto and I loved it.]
When I first went to Japan, [I could hardly understand a word of what people said.]
In the first sentence, you talk about what Japan was like for you, as a first impression. In the second sentence, you simply talk about the time period, which coincides with your arrival in Japan.