Other examples: Kidsbook, AirLyft, KidsTube, VideoHunt, MegaSoft, FunStation, etc. What’s the best way to deal with this? I can definitely be on the safe side and change the business name, but I’d love to keep what it is right now.
Ask them and get permission in writing from someone that has the authority to give you permission. If they refuse, change your name.
I've had experience with larger companies sending threatening legal letters, it's not fun and it's a waste of time.