I have to agree this is a really nice idea you have here, with lots of potential. Personally I'm not usually a fan of self-loathing (but I'm a hypocrit because I spent ages writing just that in my fics!) in fics for Willow, but I think this has a bold new way to deal with it.
Well just for example here is a English-Ukranian dictionary. You can type a few words at a time and it can translate it for you. It won't be grammatically correct but your not aiming for that, after all it's not real Ukranian you want, it's some other language. All this gives you is chance to get 'strange' but consistent words easily without making them up.
http://lingresua.tripod.com/cgi-bin/onlinedic.pl
I just googled Online Translation Ukrainian to get that, you can do it for all sorts of languages (though many results offer pay translations services, which you don't want.)
On the other hand... How far back in time are you sending Willow? You can brush over it, but if you were looking pre-America then maybe far enough back that you could find Willow in a time/place where Tara ancestors (if you extrapolate that Maclay is a Scottish/Irish name) were gaelic speakers or something. That would also give you a communications barrier but from the other side. Just something to consider if you find the barrier is more important than the reason. The thing with that is that there is at least a hint of gaelic still in English, so you have a natural basis to build from once they no longer see Willow as a monster. But it really is a change to what you suggested you want to do.
Either way, I don't think you need to worry too much about the language itself being silly. As long as you apologise to any Ukranian kittens (or whatever language you chose) you'll be okay.
Your plot 'problems' - don't give up on this. Yes, its a toughie, but it could be very rewarding for you and readers. There are all sorts of challenges you have here - both Willow existing effectively in the past and Tara in the present when she comes back. Their experiences can be mirrored to some extent. I'd love to see you explore more than the monster issue - I think you can stretch it and explore the worlds they find themselves in to the resolution of their problems. I can even see, for example, they might find some records that'll suggest the child 'died' or 'vanished' at the time along with Tara-(just to explain the disappearance) - and thus they've done the right thing in the end. They always had come through time.
Then you get into temporal paradoxes but stay away from those as much as you can and just write your story. This isn't Star Trek!
One thought that does occur to me from your potted summary is that if someone who loves Willow is the only person who doesn't see the monster then your in a little trouble. Until she does see Willow how can she see fall in love and NOT see the Monster? You might need to tweak the reasoning behind that.
And there's another reason. I think you might need to have this not be Tara's ancestor but Tara. In some way it needs to be Tara - stated as such. I only point this out cos of the Pens FAQ - all fics are about the girls, together. AU is one thing, but Tara needs to be Tara. Somehow. But you can clear that up with reincarnation/preincarnation or something! Perhaps into this life without being 'aware' of how it happened, or that it has. Willow awakens her too perhaps? The benefit of that for what I mentioned about needing love not to see the monster is that Tara, truely Tara, already has/will/does love Willow. You therefore create a perfect reason why she see's Willow and not the monster.
Two plot problems cancel out and solve each other potentially. In which case you might want that second, say gaelic, barrier between them so that can explore that rather than just the monster barrier?All this is just off the top of my head. Keep, ignore or curse any or all of it.
Last thing I'd say about potential plot logic... what does the child see? Is she going to be happy with Mom falling in love with a monster. You need to stretch your logic there if the child also needs to see Willow.
Don't mind me picking holes, I only bother because I think you have a good idea here. As long as you review the Pens FAQ to make sure you write within the guidelines (and I'm sure you were anyway - but it's just the wording of your summary) and can find a way around the logic then you can create something very interesting here.
I've rambled enough... see what you think of what I said. Happy to clarify anything that's badly explained.
Katharyn