I would always do this in the 3D app. As Dave said, just replace the still surface texture image (or whatever it’s called in MAX) with a TGA image sequence (or AVI or whatever) wherever that still image appeared in your scene.
When you need to switch images, just replace the texture again and only render the object that uses the texture … then composite that over the original animation in AE.
I wouldn’t try to track something that gets so small (even tracking from large to small), especially since the scene is CG and you have access to the app that made it.
The “pro” way is to replace the texture and re-render in MAX, but rendering as little of the scene as possible if you’re under the gun for time.