I kept getting the same error. So I downloaded all the replays that were up and checked the size. They all had less than 3MB and my 2 replays ( both below 50min) had slightly more than 3MB.
Drove the map once more, improved by 45s and the replay had 2.8MB.
I don't know what influences the size of the replay file, it can't be the length only, but what I can say is that the max replay size is 3MB