Software Bug in progmem or arduino IDE?

I am using a Mega 2560. When too many* 0xFFFF data elements are in a progmem array,an error message is issued:
" Avrdude: verification error, first mismatch at byte 0x0224. 0x00 != 0xff "

*(about 200 ints of 0xFFFF is too many)

This is not a hardware error because I swapped Arduino mega boards and same error appears.
A temporary Fix is to substitute 0xFF00 for all instances of 0xFFFF,

Does anyone have an idea why this is happening?

The Arduino Mega 2560 board did have those problems =(
The problem can be the binary code itself and also the size or the order of the memory to upload.

When you have a programmer (or use an Arduino as ISP) you can burn the bootloader.
Use Arduino IDE version 1.0.5 or 1.5.7 and burn the bootloader. That should fix it.

Sometimes a workaround does help (but not always).
You can create dummy data in flash (use PROGMEM) to go beyond the 16, or 32k or 64k flash size border.
Or you can change the memory by using the 'F()' macro for text, or by removing the 'F()' macro.

If it is hardware related or a signal goes wrong with very long 0xFFFF data, then it must be something else. I can't use my Arduino Mega 2560 now to check it.

Is this problem common for all Mega 2560? I have one and no problems observed, but I've uploaded only up to ~32K sketch, never more.

It was a problem, but it was fixed.
Perhaps if you have an old Arduino Mega 2560 board, or a fake/clone from Ebay with an old bootloader !

In the release notes: http://arduino.cc/en/Main/ReleaseNotes
With version 1.04: ARDUINO 1.0.4 - 2013.03.11 * Fixed a bunch of bugs on Mega2560's bootloader (Mark Sproul)

Budvar10, when you get above the 32k border, it probably will work, even with an old bootloader. Only in a few cases there might be a problem. If that happens, sometimes a workaround is to declare dummy data to push it over the next border (code size above 64k).

A programmer is needed to burn the new bootloader.