Does it engage by hand easily? If not then a new spring isn't going to do it either most likely.
And another spring won't be an easy thing to find unless you have a spare set of hubs laying around for parts. If it's the spring that's whacked out, you should probably just get new hubs. If you're the original purchaser, they would be covered under the lifetime warranty anyway.
If not, then maybe someone's got an old set they're throwing away that you can scavenge things from.
When you're testing for locking, are they in or out of the vehicle? Are you making sure that the inner sleeve's splines are lined up with the gear by spinning it? If they're not, then the steel gear won't slide in the aluminum splines.
You probably know that and tried it, but I figured I'd mention it anyway.
How easy is it to push the steel gear into the aluminum slug? It should glide pretty easily, but with some resistance from that inner spring. It'll wobble in the slug of course, but it shouldn't get cocked off sideways enough to bind things up. On the other hand, if the inner sleeve is all worn out and getting cocked off-center, then the steel gear may not slide over it either.
So check the inner axle sleeve to make sure it's not all wobbly (very common wear item) and maybe causing trouble.
You've probably already messed with all that since you've had it apart, but those are the only things I can think of. They're not generally considered repariable items, and Warn does not usually sell individual replacement pieces. Even their "rebuild" kits are usually just new screws and seals, but you can check with them to see if new springs come in them nowadays too. If you try to buy pieces, or warranty them directly (as opposed to through a retail store), they'll usually just sell you the whole assembly, minus the knob set.
One more thing. If you're testing this on the vehicle, how are your wheel bearings? If they're loose enough, their could be enough pressure on the hub pieces to allow them to bind up slightly. It's a long-shot, but probably possible.
Good luck.
Paul