Look in the properties of the BlackBerry Server (there is a manager utility available...sorry I don't have access to any of that right now) and confirm each of the settings. Also, put your POA into Verbose logging if it isn't already and watch to see if you see any lines in the logs about RIM or BlackBerry and trusted app. If you see those words, then the BES is successfully connecting to the POA.
One other thought. Do you have the GroupWise client installed on the BES server? If so, which one? Version 6.5 uses API calls to the POA and version 7 uses SOAP over port 7191. If you're using ver 7 make sure that SOAP is enabled on the POA (it is NOT by default).
Scott