It took 6 months to get my I765 application (filed 12/4/02) approved. It was my first applicaton. It's definitely not unheard of to wait that long, although not typical. I am from an NSEERs country, but interestingly I did not get any RFEs. Be prepared for a long wait, and file a MINIMUM of 90 days before you need it. I plan on filing for the next one 6 months before my current EADs expiration date.
PS21, you can try getting an interim EAD in a couple of weeks from your local BCIS office (if you need it).
rgds,
sadiq