I had the same situation (transactional replication from SQL 2005 to SQL 2000), the same error message and a huge waste of time.

The solution was to delete the source database...