I think it is a war saying from when the uniform was stripped off a dead soldier and put on someone on the opposite side to help them escape or whatever
The saying, of course, means that the advantage has changed sides. "Now you're not top dog and I am!"...sort of thing. Obviously, I am not saying the previous answer is wrong, but I'd imagine that it just means "Whereas you were in a position to kick me, now it's my turn to kick you!" In other words, the kicking-boot has moved from one person's foot to another.
I should have added above that the earliest recorded use of the phrase, in the exact form 'the boot is on the other foot', appeared in the 1860s in a book entitled Women of War by F Moore.
The idea had been used earlier to suggest that someone had got the wrong end of the stick...ie misunderstood the situation...which is not quite the same thing.