App Re-branding

We would like to re-brand an existing app but continue allowing downloads for the old branded app as it's tied to print media that will be around for many years. Is this permissible? I was told it is not without any details, but my research says otherwise.

They are completely different brands, logos and company names but the same app.