We demonstrate four-wave-mixing based wavelength conversion at 1.55 mum in a 2.2 m-long dispersion-shifted lead-silicate holey fiber. For a pump peak power of ~6 W, a conversion efficiency of -6 dB is achieved over a 3-dB bandwidth of ~30 nm. Numerical simulations are used to predict the performance of the fiber for different experimental conditions and to address the potential of dispersion-tailored lead silicate holey fibers in wavelength conversion applications utilizing four-wave-mixing. It is shown that highly efficient and broadband wavelength conversion, covering the entire C-band, can be achieved for such fibers at reasonable optical pump powers and for fiber lengths as short as ~2 m.