I was not aware of applying for the NARA documents first and I have requested my USCIS search in Feb. 2012- still do not have a response. The website has had the following disclaimer since April;
Index Search (G-1041) Requests are now being worked as received. Replies are generally mailed within 3 to 4 weeks.
Record Requests (G-1041A) received in January 2012.
Older Record Requests not yet closed are awaiting files or privacy screening. If you submitted a Record Request (G-1041A) prior to January 1, 2012 and have not received a file/response, you may contact us at the email address below.
Questions about the USCIS Genealogy Program may be sent to Genealogy.USCIS@dhs.gov.
Last updated: 04/17/2012
I emailed them in 06/12 asking for an update and did not receive a response- anyone have any suggestions for my next step? My appt is in 11/12