OK, I figured it out! After trying to install it on my G1 through Eclipse, I got an error message about keys not matching. Now, I know that you must uninstall the same app before you install with a different key, so I thought this was odd since I had already uninstalled.
I Googled around and found that sometimes a little data somehow remains after an uninstall. So, the fix was to reinstall the app with the last key I used and then uninstall again to try to get it to completely uninstall. After that, everything worked!
Thanks for your help nmc for trying to help me figure this out!