-It is strange for this IO who thought your 结婚证 is not the evidence of your marriage. Anyway, you have to do what the IO ask you to do. You may do the 婚姻状况公证 again (ask the 国内公证处 to do 结婚公证, i.e. 公证证词上直接证明,并贴照片)。
I find some information here on how to get the 婚姻状况公证 in China for your reference :
http://shbz.beijing.cn/fuwu/bjgzfwzn/
http://www.xiangtan.gov.cn/new/ggfws/hysy/hy/hygz/content_5428.html
http://www.sh-notary.gov.cn/guide/notary/marriage_notary.html
http://bbs.eueueu.com/thread-386042-1-1.html
以下是移民局原文:
The marriage certificate issued by the Marriage Register of xxx districe which was submitted with the initial filing is not acceptable evidence of your relationship to the principle alien. You must submit a notarial marriage certificate that specifically attests to the marriage of xxx and xxx to include the date of marriage.