El escudo NFC de SeeedStudio utiliza SPI para comunicarse con Arduino. Una opción simple es quitar el escudo del Arduino, cablear un conjunto alternativo de pines en el Arduino Mega para el SPI que golpea a los bits y verificar si aún hay conflictos.
No estoy familiarizado con la biblioteca AndroidAccessory, pero si esta biblioteca inicializa o usa los pines utilizados por la biblioteca PN532 para SPI por cualquier motivo, o si está utilizando SPI para algún propósito, la biblioteca puede entrar en conflicto con el escudo NFC.
Uno podría intentar cambiar la secuencia de las llamadas de inicialización de las dos bibliotecas, en caso de que una u otra biblioteca esté realizando una inicialización general que anule algunas configuraciones de pin e impacte en la otra.
Para investigar más a fondo, uno tendría que examinar el código o la documentación de la biblioteca de accesorios de Android. La biblioteca PN532 es relativamente simple, por lo que revisar su código no es demasiado complicado.
Otro problema potencial podría ser una memoria insuficiente para que ambas bibliotecas operen simultáneamente, menos probable en el Mega 2560 que en el microcontrolador más pequeño del Arduino Uno, por ejemplo.