Ok, in case anyone else runs into this issue, two things going on here:
1. Blackberry 4.1 phones always display the warning 'This application does not contain a signature. It might not be from a trusted source. Do you want to proceed?' when installing OTA:
Knowledge Center - This application does not contain a signature
2. When signing 4.1 applications it is best to use the 4.3 tools (since you get the nice '-p passphrase' option for the SignatureTool.jar), however, if you do so, don't forget to copy the sigtool.bat, sigtool.csk, sigtool.db
and the SignatureTool.jar from the 4.3 bin to the 4.1 bin. Reference:
Knowledge Center - Signature Key format changes in BlackBerry JDE 4.3.0