I feel a little strange making my first comment about any of the stories be a negative one, since, like contra, I have liked far more stories put out by Escape Pod than I didn't like. I also usually prefer to assert what I love instead of go on about what I don't like, but I have to admit, I did not like this story at all.
There are a couple of bright spots I can point to: the aliens not getting things quite right was one of them (the down shrug was great) and that moment when the guy stands in the backyard staring at the birds was choice, too.
Overall, though, I found myself picking and picking at the story for logical fallacies (at first it sounds like you have to be really observant to pick out aliens, but who would fail to notice some of the things the main character notices? So, he doesn't believe in aliens, but he's packing his bags anyway? Zuh?) and going completely into crit mode (this point of view is unsatisfying, if the story is about his journey, why are we in her head? -- to which the answer is, near as I can tell, so we can have dramatic sacrifice at the end. Or, how come you got to tell me how big and great and special their love is but you can't provide even a single example of such within the story?) combined with cringing before the end (please, not the self-sacrificing twu wuv, please, no, no, -- blech).
Ultimately, I think the major flaw of the story, the thing that allows me to pick and pick and pick, is that it doesn't move fast enough. It's way too long and too much of the prose is explanation, not in the moment feeling, action, reaction.