I´m very glad that I don´t have the Steam version of Civ 3 Complete with its unbelievable bugged labelstext file.
This said, the normal format for the icons for the civilopedia are 128x128 (large) and 32x32 (small), pcx, 256 colours, the last two colours in the palette when using PSP are magenta and 'poison'-green (see screenshot). The most common error is, that the image has 16Mio colours instead of 256 (in that case the icon in the game will be completly black).
You should also have a look into your pediaicons text file in the text folder, if the used icons have the proper spelling in that text file.