The loading.bmp (and the exiting.bmp which is often ignored depending on your iGo/Primo version, but you can replace that too, if you like) can be three different places. Depending on a number of factors, it may be necessary to replace all of them (assuming all 3 locations exist on your file system).
1) inside data.zip.....ui_igo8 (for iGo 8x)\ ui_igo9 (for Primo)\{system_resolution}\loading.bmp
2) inside branding.zip (same location as above), and also in {system_resolution}\skin_night\loading.bmp
3) If your system has a ui_igo{8 or 9} folder in the main folder root, then same locations as above.
Basically, you want to replace loading.bmp in ALL the locations it can be found, so that there is no chance any other than the one you want is used.
Be careful when dealing with data.zip and branding.zip files not to completely decompress them, make changes, and then re-zip them. This may render them useless and unable to be read by iGo/Primo. Only work with such files within Winrar by using drag/drop within the Winrar interface. That way, the integrity of the archive is preserved so that iGo/Primo can use it.
Sometimes (not always) it may also be necessary to delete the Save folder after making changes in order for those changes to be seen.