I followed the advice here and sent an email addressed to the CEO and the President of Staples, expressing my disappointment with their ability to fulfill their offer.
I just got a call from them.
They apologized and they're selling me the Navigon 5100 GPS at a price, after $50 rebate, that's the same as the one that was advertised for the 2100.