Hajj as a revert

Assalamu Alaikum,

If you go through a reputable hajj company, they should know exactly what the Saudis require. The Sacred Caravan Umrah group has a new muslim certificate that they require converts to submit, so I imagine that's proof enough for the Saudis that you're muslim.

This is what the conversion certificate I got from al Azhar looks like. The underlined portions were fill in the blank:

In the Name of Allah, the Beneficent, the Merciful

Certificate of Embracing the Islamic Faith

Praise be to Allah; peace and blessings be upon His prophets and Messengers and upon the final prophet and Messenger Muhammad (P.B.UH) Al Azhar Administration hereby certifies that:

Miss. My Name

of American NATIONALITY, who had been previously an adherent to Christian, Protestant, has presented herself today 5/6/1424. A.H. (Corresponding to 13/8/2003 A.D.) expressing her desire to authenticate her embracing the Islamic Faith. (I made them write a note in here in arabic that I had converted some time earlier).

In view of the fact that the applicant has convinced us of her identity by presenting the appropriate documentary, we have discussed several points with her to make sure that sincerity is deeply rooted in her desire, we have further explained to her in general the principles and the essense of Islam, its pillars, the lawful and the unlawful in accordance with Islamic legislation (shari’ah)

She, henceforth, reiterated her acknowledgment of the Islamic Faith, saying:

أشهد أن لا إله إلاَّ الله و أشهد أن محمد رسول الله
I bear witness that there is no god but Allah and I bear witness that Muhammad is his servant and Messenger.

I also acknowledge that Moses, Jesus and all other Prophets are servants and Messengers of Allah. I renounce all religions other than Islam. Furthermore, I hereby and henceforth adhere to Islam as my Faith and Shari’ah.

Having realized that she has adopted Islam by her own free will, we have informed her of the rights and obligations of a Muslim. She has chosen a Muslim name as:

(I didn’t change my name, so I didn’t write anything in here)

This certificate has been issued to the above mentioned, in order to authenticate her adoption of Islam and her decision to act in conformity with its provisions.

May Allah, the Almighty, guide him permanently along the straight path. Verily Allah is the best Guide.

Declared by: (my signature)
Authenticator: (signature)
Sheikul Azhar Al Sharief: (here I have Tantawi’s autograph, ha)

inshaAllah AbuS and I will be making hajj in 2011, and will start researching everything soon, so I guess I'll find out soon

I did not know you need certified paper proof to be acknowledged as a muslim?