When my dealer replaced my Nav system under warranty, he forgot to program it for the stock wheels on my car, and I had the same problem with a COMAND 2.5 unit. This is different from the tire size programming that you can do in the COMAND "Navi Settings - Calibration" menu.
Since you have entered your proper tire size, and whether they are new or used, into COMAND, and it didn't solve the problem, the dealer will have to do the rest.
Incidentally, if you don't have a COMAND user manual, Paul Dick has posted them at http://home.earthlink.net/~phdwebsite/comand_manual.htm
Firmware can be a problem; the firmware update discs are listed as tools (not parts) and are made available to the service department. Dealer "parts" departments will likely not have a clue. Try contacting your dealer's telematics tech, and see if he can order one for you. Also, listen to any cautions he gives you about "Flash updates" (firmware updates). If he is cautious, he may not be able to help you out of a bind if the update wasn't correct for your COMAND or car.
You don't say whether your COMAND is U.S. or European - there is a download for European COMAND updates somewhere on the Web - you'll have to search the forums for it. However, it won't work for U.S. COMAND systems, and the same cautionary advice applies from the preceding paragraph.