Did you take normal weapons, or ones that already have some kind of power? I was able to get a weapon enchanted at my first attempt - I think it was just a longsword. Maybe the material has something to do with it.
Locations of trainers are spoilers! (I know you weren't spoiling, but answering would be )