Adobe AIR Mac app returns 'code failed to satisfy specified code requirement'

We followed updated codesign process to prepare Mac App to App Store discussed at here: https://forums.adobe.com/thread/1909626

Initially I tried to codesign our Adobe AIR Mac app with Mac Developer distribution certificate which generally starts as "3rd Parth Mac Developer Application:xxx". Later, I read through https://developer.apple.com/library/mac/technotes/tn2206/_index.html#//apple_ref/doc/uid/DTS40007919-CH1-TNTAG211 where it's discussed that verification through codesign and spctl commands needs the certificate to be Developer ID certificate only (I'm using 'Developer ID Application:xxx'):

Like Gatekeeper, spctl will only accept Developer ID-signed apps and apps downloaded from the Mac App Store by default. It will reject apps signed with Mac App Store development or distribution certificates.

My verification commands were:

./check-signature DEPLOY/Moonshine.app DEPLOY/Application.pkg 

(c) 2014 Apple Inc. All rights reserved.
DEPLOY/Application.app: YES
DEPLOY/Application.pkg: YES

and

spctl -a -t exec -vv DEPLOY/Application.app 

DEPLOY/Application.app: accepted
source=Developer ID
override=security disabled
origin=Developer ID Application: xxx (LS9K97G9DD)

Both commands were retuned positive results as discussed in Apple Developers page.

When we submitted the app to App Store we returned with errors like "test-requirement: code failed to satisfy specified code requirement(s)". We also supplied with suggested (Code Requirements) links by Apple: https://developer.apple.com/library/mac/technotes/tn2206/_index.html#//apple_ref/doc/uid/DTS40007919-CH1-TNTAG4, and we started verifying .app file at our local with following command:

codesign -vvvv -R="anchor apple" DEPLOY/Applications.app 

We starts receiving likewise error as Apple sent us:

--prepared:/Users/santanu/Documents/Adobe Flash Builder 4.7/ProjectFolder/build/DEPLOY/Application.app/Contents/Frameworks/Adobe AIR.framework/Versions/Current/. --validated:/Users/santanu/Documents/Adobe Flash Builder 4.7/ProjectFolder/build/DEPLOY/Application.app/Contents/Frameworks/Adobe AIR.framework/Versions/Current/.
DEPLOY/Application.app/: valid on disk
DEPLOY/Application.app/: satisfies its Designated Requirement
test-requirement: code failed to satisfy specified code requirement(s)

Later, I also tried to codesign with Mac Developer distribution certificate (3rd Party Mac Developer Application:xxx) instead of Developer ID certificate, but that didn't improve the situation either.

I'm unable to understand now what else certificate we should use to get that anchor apple in our codesign process to fix this 'code failed to satisfy specified code requirement' error, or any other way we can fix this?