gmpthat I downloaded were likely not compatible, and were causing problems.
After some searching on the net I found that inside gcc source tree, there is a folder called contrib which contains a script called
download_prerequisites. So, all I needed to do was to get into gcc source folder and execute:
This downloaded the correct versions of the prerequisites and I was then able to successfully build the i586-elf target gcc cross compiler.