People would get problems resolved a lot faster if they'd post their patches so we could see your problem and tell you what it is from the start.
If you converted or preserved your image in .BLP format and reconstructed the filepath and filename to overwrite the old files then the only issue would be that your game client is still reading the old files.Make sure your MPQ patch is being read by the client and that you actually overwrote the old textures in your archive. Texture sizes vary more in WOD so be mindful of which version you're editing these for too.
Don't forget to add a _s file. Without that, you would see the old texture over your new one.