I agree. The second the OP mentioned that he would need a visa and that this was a new startup, I assumed they let him go because they were naive about US visas at the beginning. They are not an easy process; typically a work visa will require a lot of money in filing fees and several months of paperwork, often including a labor survey to ensure that the position could not be filled with an American instead.