This is a really good story--I tend to like Cat's stories, so that's no huge shocker.
Fantasy? Only in a certain light. It's fantasy in the same way that Big Fish is fantasy. I know that the fantasy elements are not true in the strictest sense, but they exist in some respects, and that is enough for me. I like that Podcastle keeps an open mind, allowing all sorts of fantasy in, even that which is a tad metaphorical.
This had a lot of good emotions, and I didn't see the wing tattoos coming, though afterwards I wondered how I missed it. The descriptions of each set of wings were lovely details.