Finally was able to figure it out. I enabled Application logging in the Service App. Following this I saw this error "Application with <GUID> was not found in Bot Framework". Finally I remembered that when I created the App Registration, I had changed the the "Supported Account Types" from "Accounts in any organizational directory (Any Azure AD directory - Multitenant)" to "Accounts in this organizational directory only (Org only - Single tenant)". After that the echo bot began working.
This article helped - http://thewindowsupdate.com/2019/08/19/how-to-create-an-app-registration-in-azure-ad-for-a-bot-solution/