@bones: You're probably not using factor increments of the resolution. In layman's terms, your custom textures MUST be either the original resolution, double the resolution, or quadruple the resolution. Later builds of Aristotle's plugin support up to 128 times the original resolution, though it's recommended you stick to 4x. I seriously recommend against using the old Rice's Video Plugin 6.1.1 beta 11 (chances are, that's what most of you are using); try to find the 1964 Aristotle's plugin, it has MUCH better performance in loading textures correctly and quickly as well as extra dumping/loading options. It's not very hard to find; a quick Google search should give you the results you're looking for.
EDIT: dororo beat me to it; apparently someone on this forum DOES know about it. Go update your Rice.