This question and answer apply to Minecraft 1.4.7 and earlier. Minecraft 1.5 and later support high-resolution textures automatically, and do not exhibit the misplaced animations described below.
Minecraft versions before 1.5 were not written to support different-resolution textures.
The default Minecraft terrain texture in these versions is a 256×256 image with 16×16 tiles in it (a texture atlas).
The code which animates the animated textures in Minecraft (fire, water, lava, and portals) writes onto specific pixel offsets according to 16×16 tiles, which are wrong for larger textures, so you get small fire/water/portal images occupying other blocks. Presumably the patchers replace the 16× factors with 32×, or whatever fits the actual texture resolution.
The reason the textures mostly work is that the OpenGL 3D API used by Minecraft mostly takes coordinates in textures in terms of numbers between 0 and 1, rather than 0 and whatever the pixel size of the image is, so the main rendering doesn't care; only the animated textures, which are actually defined in terms of recalculating individual pixels and modifying the data of the texture in memory, are affected.
Also, tiles over a certain size (128×128, I think) will crash Minecraft. Below that size, you can still use HD textures and it will work except for the misplaced animations. The animated items will not animate, and (for a 32× pack) these will have animations on them: bricks, gold blocks, Netherrack, and pumpkins.