Stephen - per your example, what if the army you were being told to submit to and serve was the nazi regime or some modern version of that? Would your answer still be the same?
No.
Would you have submitted to Hitler as a civilian?
I think the following teaching provides some very good points on such matters
http://www.marshillchurch.org/media/trial/submission-to-ungodly-authority
Back to those authorities who wield the "sword" and the tax collectors mentioned in Romans 13, can only unbelievers be in such employ, even though they are these authorities are clearly "established by God"? Is the authority of the sword inherently wrong or God ordained? Likewise, is taxation Godly?
Blessings in Christ,
Stephen