It sounds like a bug on the handset to me, the TCK tests used to verify j2me libraries are pretty weak so lots of bugs like this find their way through.
It seems that the key is in the permissions, so I would try and play around in this area. Make sure you have the right permissions set in the .jad (before signing), if you can get hold of one try to sign with a certificate in a different security domain or certificate, try changing the permission level before running the applet.
I would expect that you'll only be able to work around the problem, so rather than suggest something specific I would be varying things within those areas.