Ask HN: Startup promised me a job, then backed out after the internship
TL;DR; Student from Europe, did an internship in a NYC startup, got promised to be hired. After having made all the plans for moving to US, the offer was retracted.

In August I began an internship at a New York startup. Since I’m European, I had no expectations that it would have led to a full-time job, given the hassle of getting an H1B visa (in fact, I was already surprised that the company sponsored my J-1 for the length of the internship).

After just a few weeks, the company was impressed with my performance (they told me I had already accomplished more than they expected from the whole three months) and they gave me a full-time offer. Compensation, option, benefits, visa paperwork, all there.
I took some time to decide, as I was considering other opportunities, and eventually accepted.

My girlfriend is American (we met in the UK, where we both did our master’s), and this was the best opportunity to keep living with her, with a nice, well-payed job in a cool town in the US.
She stopped arranging for a post-study work visa in the UK. I refused opportunities with Google, Bing, and two startups. I told all those people I wasn’t able to consider any offer, since I had already accepted one (so I thought).

The last day of my internship we made the last arrangements for my return.
I had a conversation with the main engineer, who also mentioned that the company could request a green card for me after a few years on the H1B. I received greetings and “see you soon” from everyone, including the founder.

Yesterday I received a phone call from the founder, saying that they "changed their mind", and they are stopping the visa application.
He mentioned that, for that position, they want someone more experienced with web development and UX. He added that they expected something more from the last part of my internship.

I’m shocked.

No one ever gave me a hint that I was doing something wrong. The founder himself had called me several times to show the prototype I was developing to investors.

I cannot stress how unfortunate this is for me. I was making plans to live in the US with my girlfriend. I left some of my stuff in the city. I even lost the opportunity to apply to the green card lottery, since it closed yesterday.
If I didn’t know I had a job, I would have spent the past two months looking for one, preparing for interviews, moving forward with the other possibilities I had.
My girlfriend would have applied for a visa in the UK, since I was more likely to get a job there.

I am now in the US for a couple of weeks, using the grace period included in my J-1 visa to travel with my girlfriend. At the end of November I will have to leave the country.

I’m a Mathematics graduate, with good programming skills, knowledge of CS, experience with machine learning and information retrieval.
I need to find a job in the US. It doesn’t necessarily have to be a startup, I will go for a big corporation if that makes it easier to obtain a visa.
I’m also interested in any subtleties regarding visas: is there a way I can come back as a tourist and apply for jobs? Can my girlfriend do the same in the UK (or even just move there with me until she can apply and obtain a work permit)?

Any advice? Similar experiences?