Well, this team is pretty darn old, so this answer is probably going to turn out to be a bit more geared toward revising the team.
Well to start out, Deoxys-S went from OU to Uber in the time frame from when this team was created, to current day. Although we don't need a new lead.
The first thing I'm going to say would probably work well, would be making Weavile your lead. Then make the following changes.
Okay, since we're playing him as your lead give him Low Kick instead of Brick Break.
This let's him KO Tyranitar a lot easier. As you probably know, most leads aren't hazard setters anymore. That kind of gameplay just kinda made it's way out of the meta-game to where now people set up their hazards mid-game, or if they're running sand put it on their weather setter. So the main lead you're going to see setting up hazards is Tyranitar.
Now this is a nice little thing I can see here, making Starmie more bulky and long lasting, but still making him be able to abuse that speed.
Starmie @ Leftovers
Trait: Natural Cure
EVs: 252 HP / 4 SDef / 252 Spd
Timid Nature (+Spd, -Atk)
- Hydro Pump
- Ice Beam
- Rapid Spin
A guy on smogon gave me this set for one of my teams and it worked wonders. Turns out Starmie can be pretty bulky, and adding Recover onto that can make him a Rapid Spinner that will last you the entire match. You have enough sweepers as it is :P
Well this is what I'm recommending your Deoxys-S replacement be. Starmie is a really nice long lasting spinner choice, so you shouldn't have to worry much about Stealth Rocks killing off your Volcarona. You also lacked a special set up sweeper, or a reliable way to take down things like Ferrothorn, Scizor, and Forretress ( although a boosted Low Kick from Weavile could probably do some nice damage on Ferrothorn )
Ability: Flame Body
Nature: Modest / Timid ( Your choice )
EVs: 4 HP / 252 Sp atk / 252 Speed
Roost / Giga Drain
After using Quiver Dance, Volcarona becomes a bit of a speed freak being able to out speed a lot of threats. 2 Quiver Dances makes him generally faster than all of your common threats ( even with scarfs equipped )
The moveset is very self-explanitory. Although Roost and Giga Drain are BOTH BW2 moves, so if you aren't interested in any of that you can probably run something like HP Ground for Fire type opponents that generally wall this set if you don't boost high enough.
This being the step in for Deoxys-S who is now Uber in both PO and Smogon tiers.
Looks great. Hypnosis > Steel Wing can make him more annoying. Especially considering STAB Acrobatics with no item does more damage than a super-effective Steel Wing. And is more accurate. You could also throw something like Taunt in there.
He's not going to be taking much hurt from status that would benefit Quick Feet, so having more electricity protection in your team wouldn't hurt. Besides that, it's a solid set.
Also looks great! A little bit of bulk never hurt.