I have received the error you describe, but only in case the device already have the application installed and it is signed with different key. When you install from Eclipse it automatically signs your apk before installing, but the key will be different from the one that will be used when using the export wizard.
Couple of more reasons why your install might fail:
- If there is no sufficient storage on the phone, though I assume that there should be more user friendly error for that
- If you have not allowed installation of applications from unknown sources. Here is description in pictures of how you do that.
Also consider looking into this thread if the other suggestions do not help you.