That certainly sounds like a grounding problem. If you happen to have one lying about, try adding a (3-connector, this is important) minijack extension lead between the mini and the headphones, and see if this still occurs. If the problem is an odd socket layout in the mini causing the ground to be connected improperly, then this should solve the problem. If the problem is the mini's internal wiring, I can't think of a way to fix it other than sending it in for repair. On the other hand, it could still be some odd wiring in the headphones themselves. If you can test with some other headphones, that would narrow things down.
Either way, I think the problem comes from using headphones with a 4-connector minijack in a standard 3-connector socket.