really strange:
the teture you wanted to replace was originally inside the Addon folder or it was something like: \data\xyz.paa ?
If it is the last one, you have to uncompress DATA.pbo and take the file you need (no insurance about working).
Otherwise... check first of all if the path is correct and there are no writing errors... it usually happens (dozen to me ;D ).