Really? That's weird. I've been using this Uxie set:
Uxie @ Leftovers
Nature: Calm
Ability: Levitate
EVs: 252 HP | 16 Def | 240 Spe
- Stealth Rock
- Thunder Wave
- U-turn
- Grass Knot
Against the Utility Omastar on site, Grass Knot does 47.7% - 57%, which is a decent chance to 2HKO. Against 252 HP/0 SpD Omastar leads, it does 53.5% - 64%, an obvious 2HKO. At most, they're getting a single layer of Spikes, which they would have gotten regardless, or Stealth Rock (even better for me). You must be facing some weird Omastars that invest heavily in SpD, or those lame-ass Rindo Berry Omastar.
I've never even had a slight problem against Omastar. Grass Knot 2HKO, Thunder Wave the switch-in, Stealth Rock/U-turn, and move from there.