There is a workaround available: Git Hub Issue

In a nutshell they create a new temporary VPC and associate both Cloudmap NS and Route53 Hosted Zone with it. And then simply change the Hosted Zone association from temp VPC to shared VPC by using some AWS CLI commands. That worked in my case