I'm running a 32gb class 4 card in my phone with no problems.
Are you saying that the <i>same files</i> work on the 16gb card, but not the 32gb card? I'm having a hard time with that idea; the card doesn't care what the file is; its only job is to store the bits.
It is possible that you're hitting a bad spot on the chip, and that the larger video files happen to be the ones hitting the bad spot, but I've never actually heard of an SD card that "sort of" works; every one I've ever had has either worked or not worked.
If you're having trouble with video files in general, the problem is more likely the encoding of the video files. If you're trying to view downloaded movies, you could be hitting unsupported resolutions, bit rates, or encoding schemes. There also seems to be a wide variation in h.264 encoders, so some will work great and others will fail miserably.
One thing you could do is find an encoder that works for you, then run any movies you acquire through that encoder to ensure that you have a uniform resolution, bit rate, and h.264 encoding setting.