I have not been able to download a midlet larger than 32kb into an actual Nokia phone. I have tried the Nokia 3510i and the Nokia 7210. Midlets less than about 31.5kb work fine, but when I increase the size of the midlet slightly, I get an incomprehensible error message like "No server access". With the emulators and with other phones, such as the Siemens M50, midlets larger than 32kb work fine.
Is there a hard limit of 32kb for the size of a midlet in Nokia phones?
I'm not sure about the 3510i phone, but for the Nokia 7210 and sister Series 40 phones the game size can be up to 65Kb.
Go to this site, http://www.forum.nokia.com/main/1,,1_0_55,00.html, it provides full specifications on each Nokia phone currently on the market.
As dmford wrote those phones accept larger jar files.
I guess the reason to your problem is that the WAP gateway you are using does not let go through large files. The limit seems to be 32 kB. You can ask more information from your operator.
I do not know how Siemens M50 works but I guess it doesn't use WAP gateway when it downloads MIDlets.