Bitcoin Cash (BCH) changed its address format starting on January 2018. One of the reasons this upgrade took place is to prevent users from accidentally sending funds to a BTC wallet and possibly losing funds.
The address format will change from the one used by Bitcoin (14yptfjp6coctaVYcyD9cbYNJaBjve2Nf8) to one that looks like this: qq460fspwj8t3w4q49ln496qftkfwutqyg6n30d4xr
When sending to the old address format, it is automatically converted to the new one on the confirmation screen. Don't worry, the address format is just an encoding. The receiving wallet represented by it is the same.
Both addresses correspond to the same public key. They are, in essence, the same.
My exchange / other wallet doesn't accept my address. What do I do?
You can use this converter tool to check that both old and new addresses are the same. If you want to share your new address to a wallet that doesn't yet support it, you can also use it to convert to the old format.
If you have more questions, please read the FAQ created by the developers: https://www.bitcoinabc.org/cashaddr. We will gladly answer any other questions not covered by that page.
For technical specifications, please refer to the github page: https://github.com/Bitcoin-UAHF/spec/blob/master/cashaddr.md
Note that some providers such as other wallets and exchanges might not have updated to the new format yet. Theoretically there should be no problem sending from a "new" Coinomi BCH wallet to an old (legacy) address on one of those providers, but users are advised to seek consultation from the support teams of those services too before sending.