Most non-Apple systems usually only are able to handle FAT32. Many will handle NTFS or EXFAT as well.
FAT32 is limited to a file size of 4GB max per file. HFS+ (what you used) will hold the files, but it won't be recognized. You concluded this correctly.
Try either NTFS or EXFAT. For NTFS formatting you will need a Windows or a current Linux system which can write to NTFS. Another alternative would be to install NTFS drivers with write permissions in your OS X setup, but I'd consider this the least preferred option.
Long story cut short:
- Try formatting the drive as EXFAT and see if that works
- Try formatting the drive as NTFS and writing the file within Windows or a modern Linux setup
- Try splitting the file without re-encoding with special software. You could Google some programs, as I must admit I cannot recommend any right now
3) wouldn't be a true solution but a workaround, so I'll not do a lot of research now, hoping option 1) or 2) do help.