Learn Russian: Мы изменили план в последнюю минуту.

Because this is an active sentence where the subject (Мы) is doing the action to a direct object (план). If you wanted to say that the plan changed passively or on its own, you would use the reflexive form instead: План изменился.

Why is 'at the last minute' translated with в plus the Accusative case (в последнюю минуту)?

When talking about a specific point in time using words like minute, second, or days of the week, Russian usually uses в + Accusative case. Since минута is a feminine noun, both the adjective and the noun take the feminine Accusative endings (-ую and -у).

Why use the perfective verb изменили instead of an imperfective like изменяли or меняли?

Because changing the plan was a single, successfully completed action with a clear result in the past. If you used the imperfective, it would mean you were in the process of changing the plan, or that you used to change it repeatedly.

Could I use поменяли instead of изменили here?

Yes, in everyday speech Мы поменяли план is very common and means the same thing. Technically, изменить focuses on altering the details of something, while поменять can imply swapping something out entirely for a new one, but for plans, they are practically interchangeable.