Background
The group I work with has been using and developing a Python package, which for the purposes of this question I'll call foobuilder. We serve updates for Linux systems using private RPM and Deb repositories we provide for our users.
Recently, a public package was added to PyPi with the same name. It also got packaged on the public Debian repository, among other places. Since we don't publicly advertise our package, it's understandable that a package with the same name has popped up.
Concerns
This looks like a big problem for foobuilder because somewhere down the line, a user might try to install our foobuilder while the public foobuilder package is installed on the same system.
Besides the obvious problem in Python, I would guess that adding our repository to a Debian package manager program could also cause some issues, though I haven't played around with this situation yet.
Problem
Since we've been using the proprietary foobuilder for years, there is a ton of code in existence which wants to import foobuilder and expects to get our package, so I don't think it's feasible to change the name.
My thoughts on possible solutions
Python
I've considered changing the name of the package to my_foobuilder, and having it include a meta-package called foobuilder which consists only of an __init__.py that imports everything from my_foobuilder. I could instruct new users to import my_foobuilder directly. Then I could begin to deprecate the foobuilder name. In the end this would result in the same amount of work as if I changed foobuilder to my_foobuilder now, since everyone needs to be served updates and the foobuilder name can't be in deprecation purgatory forever.
Debian
The Debian problem shouldn't be too hard to solve; I can change the debian package name to my_foobuilder but have it still install the same (conflicting) Python package. I could then set the my_foobuilder package to Conflict with foobuilder. It might require users to fiddle around with their package manager to get things back on track during the transition but I don't think that's a big deal. Still, this prevents users from using the public foobuilder package at the same time.
Question
Is there an easier or better way to treat this situation than what I've considered above? Are there any problems with the solutions I'm considering? How would you deal with this?
I'd email the new foobuilder package author to discuss the problem. Obviously one of you needs to change package name; due to proprietary nature of your program is may be undesirable to change its name... Asking this question to the new package author may come up with some new solutions. 
There really is no sane way to have Python handle this in a way so 'import foobuilder' can mean 2 things.
How to deal with a proprietary Python package name conflicting with a public one?