So I figured out the error and resolved my problem. The machine that I did the initial backup from had all my music on a second internal drive (D:\Music - Its a Windows machine). When I backed up onto a USB drive the backup function consolidated all music files onto the "Rekordbox_Bak" folder of the USB Drive (as expected). The USB drive now had all of the music consolidated onto the new "Rekordbox_Bak" folder from the former locations on my D:\Music Folder.
My new machine has a 1TB SSD with a C: Partition roughly 940GB. It also has a very small D: drive as a Windows Recovery drive. What I didn't realize is that when RB DJ does a restore on a new machine it tries to recreate the original file locations instead of prompting for a new music folder location. So it was trying to create a D:\Music folder on my new machine. Hence the error message above, because the new machine had a much smaller D: partition than the previous, even if the C: drive was much larger, RB DJ didn't care.
My only recourse was to go back to the original machine and move my music folder to my C drive, have RB DJ find all those files again, and then do another backup. This time I had no errors on the restore because RB DJ found enough space on the new machine to recreate the music folder. Now at least I was able to consolidate the files.
My files are all safe so i'm not worried about the database, but was hoping that Pulse might have an answer.