Hmm... 1 atmosphere = approx 15psi, water pressure increases approx 1 atmosphere every 10m (say 33ft), so at a depth of 1000 feet we're talking around 450psi. Rifle chamber pressures are somewhere around 30,000 to 60,000 psi (give or take a
pretty big margin). So there should be plenty of pressure left to expel the bullet.
I was wondering about the gas operated auto-load systems these rifles use, but there is this gas operated
APS rifle designed for under water use. And
this article claims the AK-47 gas operation works better under water (but uses a different system to the M16). Given that even at a 1000ft the water is still not getting close to the chamber pressure there seems reason to hope the systems might still work.
But all this still hinges on whether cartridges have survived the journey to this sort of depth.