windows 8 store app - dependency issue - certification failed

We just submitted app in windows 8 store (metro style app) and got the error:

XXX takes a dependency on Microsoft Visual C++ Runtime Package framework but is missing the framework dependency declaration in the manifest.

We had our app working fine in release version but it was not getting accepted as package so we needed to migrate our app as Windows RTM. During that we had following entry in manifest:

    <Dependencies>
        <PackageDependency Name="Microsoft.VCLibs.110"       MinVersion="11.0.0.0" />
    </Dependencies>

If we keep this, we get following error while build the app.

Error : DEP0700 : Registration of the app failed. Windows cannot install package 5d6f272d-c915-4de1-a9d6-c0c08d63ab94 because 
this package depends on another package that could not be found. This package requires minimum version 11.0.50727.1 of framework Microsoft.VCLibs.110 
published by any publisher to install. Provide the framework along with this package. (0x80073cf3) Test_App1

So we removed it and submit the app, it just got failed and gave following error.

XXXX takes a dependency on Microsoft Visual C++ Runtime Package framework but is missing the framework dependency declaration in the manifest.

We need to keep this package itself in the manifest but not getting it done.

I had similar problem. Add a reference in your project to Microsoft Visual C++ Runtime Package

Just click on project i select Add reference and find this Package. Adding this should resolve your problem