I found the answer myself :D I thought I would share it here in case anyone else was experiencing similar problems.
Basically the ALX file specified radio="GPRS" but the device.xml for the 8900 specified radio="GPRS-WLAN", so I guess the BES didn't like the inconsistency. Since I am using the same ALX file to push to lots of different devices, I decided not to change the radio to GPRS-WLAN, instead I just deleted it alltogether, and straight away the BES reported Install Required and I was able to push the app.
A side question then: is the line radio="..." actually required in the ALX file? I don't know why it was there, somebody else in the team set up the build script that creates these files when we do a release. Can I just remove it and therefore not care in the future what type of device I am trying to deploy to?