Well, obviously they were wrong. So I believe two things happened. First, you left without an approval. And second, you had to have applied for an Advance Parole, not a Re-Entry Permit. Let me explain the difference:
1) Travel Document - this is for people that cannot get a U.S. Passport because they are not U.S. Citizens but they cannot get a passport from their home country because either they have won Asylum in the U.S. or are stateless or because they are Residents in the U.S., their country has abandoned them. It is like a passport.
2) Re-Entry Permit - This allows a Lawful Permanent Resident to re-enter the U.S. after being outside for up to 2 years without abandoning their Residency.
3) Advance Parole - This allows an immigrant to enter the U.S. that either has no status in the U.S. or has appending I-485 and does not want the I-485 to be abandoned.
Unfortunately, for that to work, you had to have an approval of the Advance Parole BEFORE you left. So unless you can prove that your Advance Parole was approved before you left, you will have difficulty coming back. So you have three choices:
1) You wait for your spouse to see if she gets the Advance Parole in the mail and check the date of approval and if it dated before the date you left, then she can send it to you and you can use it to come back into the U.S.
2) The K-3 spouse visa takes 6 to 9 months.. The I-129F will cost $340 plus $420 for the I-130, and $350 for the visa processing fee. Then after you enter the U.S., you must still file a new I-485 for $1070 and wait for the marriage interview about 5 to 7 months later.
3) The CR-1 visa (or IR-1 if your marriage is more than 2 years old) takes about 1 year or so. The fees are $420 for the I-130, $330 for the visa processing fee, $88 for an Affidavit of Support fee. But once you enter the U.S., you enter as a Resident and you do not have to file (or pay for) an I-485 nor do you have to attend an additional interview. You just get your green card in the mail a few weeks later.
Here is a link to both:
I am truly sorry. I know this is not good news, but you should not have left when you did. I know immigration told you something, but you will be hard pressed to prove it and they really won't care. I wish I had better news for you.
Please let me know if you have additional questions and please do not forget to rate my service to you (not the state of the law) as that is the only way that I can get credit for my assistance to you. Even after you rate the service, I can still answer additional questions for you without additional charge. If you do rate me positively, a bonus is always appreciated. If you would like to request me in the future, just go to http://www.justanswer.com/law/expert-guillermosenmartin/. Thank you!