Mega Pro 16 mHz/5v not uploading...

I can bootload through a USBtinyISP. Could I just use the normal Mega 2560 bootloader?

That would be just fine. Did you try the normal "Arduino Mega2560 ADK" board with your sketch and FTDI? That one would be the 5v/16MHz board settings.