The SeeedStudio NFC shield uses SPI to communicate with the Arduino. One simple option is to take the shield off the Arduino, wire up an alternative set of pins on the Arduino Mega for bit-banging SPI through, and verify whether conflicts still remain.
I am not familiar with the AndroidAccessory library, but if this library initializes or uses the pins used for SPI by the PN532 library for any reason, or is using SPI for some purpose, the library may conflict with the NFC Shield.
One might attempt to change the sequence of initialization calls of the two libraries, in case one or the other library is doing some blanket initialization that overrides some pin settings and impacts the other.
To investigate this further, one would have to examine the code or documentation of the Android Accessory library. The PN532 library is relatively simple, so checking through its code is not too messy.
Another potential issue might be insufficient memory for both libraries to operate simultaneously - less likely on the Mega 2560 than on the smaller microcontroller of the Arduino Uno for instance.