Okay so i tried all of the above, but then it hit me - sometimes, due to my slow internet plan, my phone has issues looking up locations on maps when my WiFi is on. So, i figured maybe it's having some sort of connectivity issue.
I turned my WiFi OFF, let the phone switch over to the LTE network and it solved this issue for me. I immediately was able to play/record/save greetings.
Hope this helps anyone else who is stuck with this problem - quite frustrating. Don't know why the WiFi is choking it up as all my other internet dependent devices work fine (NetFlix etc).