In your question you say Presburger Arithmetic "proves its own consistency". Really? It's provably consistent, as the Wikipedia article notes, but isn't the proof done in a metalanguage? Unfortunately I'm at home for the holiday and don't have references handy, but I'd suggest looking at Peter Smith's book An Introduction to Gödel's Theorems for starters to get clear on this stuff.
I really like that book. It's in between Nagel & Newman's popular exposition and the dense presentation you find in math logic texts like Mendelson's. I recall that he specifically discusses Presburger arithmetic and the issues you raise here.
