Certificate error. Contact the application supplier.
We had signed it with the Certificate required by AT&T, we examined the root certificates on the device, we even swapped out the device and tried another, but the problem still remained. We started pulling out MIDlet-Permissions, nothing.
Finally I made a test application that did nothing and had basically no jad attributes. I signed that app, loaded it, and it worked. I started moving in changes from the real app into the test app, and quickly found that the error was in a place I would never expect. It was in the "MIDlet-Info-URL". If you include this simple jad attribute, it will not load onto the device.
I checked all of the documentation on Nokia's developer site, and I found full documentation for the MIDlet-Info-URL jad attribute, and it seemed like it should be fully supported, but it will result in that certificate error :-/
I thought it was worth a post since it wasted hours of my life, and still doesn't seem to be documented on the internet.
Good Luck!