I tried to reproduce the issue you're describing, but every package I created and compiled separately between the spec and body created valid Object ID's in the Team Coding tables.
Team Coding is designed to check out both the spec and body portions of packages and types together. The warning stating that you already have the item checked out is actually normal since you created and checked out the spec separately. The warning is simply letting you know that the spec is already checked out. If you have prompting on checkout enabled, you should see the spec object deselected and listed in red to let you know it's already checked out.
In my tests, both spec and body received valid Object ID's. The fact that in your situation you received an object ID of -1 sounds like either Toad wasn't able to successfully query the database for the object ID or the data in your Team Coding tables somehow became corrupt.
For the first issue, you can enable SQL Spooling from the Database -> Spool SQL -> Spool SQL to screen, then try to check the object back in, and see the query being run against either user_objects or all_objects to get the object ID. You can then use that query to verify the object ID in the database, and then compare its value with the one being used in the UPDATE or INSERT statement to TCX_OBJECTS to see if there's a discrepancy. That may help identify if there's a database or permissions issue.
For the latter option, you can query TCX_OBJECTS for the package name to see if there are any duplicate entries listed or any entries pointing to an invalid PROJECT_ID. If there are, as you suggested, you can remove them from the database, open Team Coding configuration window and then press OK. Team Coding should re-add them to the tables using the information in the database. I know this isn't the ideal solution, but it should help restore those entries with their proper object ID's.
If neither of these items help in identifying the cause of the issue, if you could provide a step-by-step set of instructions with as much detail as possible to recreate this scenario, that would be helpful. Unfortunately, every combination of checking out, compiling, and checking in both spec and body I've tried resulted in valid records with valid object ID's. Getting some additional details would definitely be helpful.