Not only can they co-exist, personally I think it's most effective and natural (at reaching people) if, as an intermediate step, you establish a "real" brand that includes both names.
If you're renaming from "Foo" to "Bar", rather than jumping straight to "Bar (formerly Foo)", you establish a brand "FooBar", leave it that way a long time (years?), and really cement that in people's minds. Once everyone recognizes it as "FooBar", you can later drop half and people will still recognize "Bar".
Also, if don't include both old and new monikers as first-class parts of the brand, then in communication people will sometimes drop "formerly Foo". For example, if it's a mobile app, is your app icon label going to be "Bar (formerly Foo)"? No, it's going to be "Bar". (But "FooBar" could be an app icon label.) So there will be contexts where people choose not to mention the old name, weakening the reinforcement of the connection to the old name.
If you're renaming from "Foo" to "Bar", rather than jumping straight to "Bar (formerly Foo)", you establish a brand "FooBar", leave it that way a long time (years?), and really cement that in people's minds. Once everyone recognizes it as "FooBar", you can later drop half and people will still recognize "Bar".
Also, if don't include both old and new monikers as first-class parts of the brand, then in communication people will sometimes drop "formerly Foo". For example, if it's a mobile app, is your app icon label going to be "Bar (formerly Foo)"? No, it's going to be "Bar". (But "FooBar" could be an app icon label.) So there will be contexts where people choose not to mention the old name, weakening the reinforcement of the connection to the old name.