You've done everything right so far.

The MDF file is a CD image file. You need to use eg MagicISO to open the MDF file and view the contents of the CD. Then you can extract the navboot file from the CD, change the GIF inside the navboot, and save back to the CD image

Then create a new CD using the CD image - this is the OS software CD

Then load the new software in the car by inserting the CD in the nav drive.

Do you have a Mk3 or Mk4 nav?