I've heard certain titles pluralised in apparently odd ways, such as a Secretary General being Secretaries General when plural, rather than "Secretary Generals" as I'd have guessed, and I'm wondering if there's a rule on this. For example if you were addressing two female Presidents, would is be "Madames President" (multiple females who preside over something) or "Madame Presidents" (multiple Presidents who are female)?
The general in attorney general, surgeon general, etc., is actually a postpositive adjective (i.e., an adjective that comes after the noun it modifies). The general, therefore, is the adjective general and has nothing to do with the military rank.
Theodore has it right. You would pluralize Presidents, just as you would say Honorable Justices of the Court.