Well I found out the problem. Hopefully this helps someone with the same issue. After many hours researching and testing I found that the issue is the cover art. When encoding an AAC with ffmpeg, it cannot embed the cover art in the new .m4a file, so it writes bad data to it, thus making it not readable by Rekordbox. Traktor and the other media players must just ignore this, but Rekordbox does not.
I have found a solution to encode and discard the album art and now it works in Rekordbox, albeit without the art. When encoding with iTunes, is does retain the album art, although it is a lesser quality encoder and has a max bitrate of 320 kbps and non adjustable low pass filter, whereas with the libfdk_aac encoder it is adjustable to 20Khz to lose no high end what so ever.