Android Question Installing Error

When trying to install my apk to a Android 2.1 phone I get the following error:

Parse Error
There is a problem parsing the package.

Click to expand...

On other phones/device (> 2.1) it installs 100%.

From the Android SDK Manager I have 2.2 (API 8) installed. From other posts I understand that Android is backwards compatible so 2.1 (API 7) should run fine.

1. What else could be the problem?
2. What is the best API to have installed or must I have more than one installed?