I'm still a bit of an Arduino n00b, but I have been flying RC planes and helis for years. I have considered an autopilot/drone project myself, the Arduino is ideal for this purpose.
The main advice I can offer on your approach is to program the autopilot a little more like you fly the plane. Halving the roll error as you're doing, for instance, means your plane theoretically will never actually level itself, as it just keeps halving the error without actually eliminating it. In The Real World (tm) of course, chances are the plane will get bounced past neutral as you get the error smaller and smaller. But the concept still holds, it seems like this would yield sluggish recovery response, possibly not enough to overcome the airplane's actual upset. This depends largely on the geometry and control throws of your plane, though...if you are not getting the recovery you want, why not just increase your rate of correct? Go 1:1 on the roll angle vs servo position, rather than 2:1.
But back to my point on making the autopilot fly more like you: when you want to change bank angle, it really doesn't matter if the desired change is 20* or 120*, you are probably going to throw in a similar amount of aileron to get the response you want. And you won't gradually reduce aileron deflection with bank angle until you are very close to the bank angle you want....actually for a lot of flying types, you may leave the aileron angle at a pretty extreme deflection, and quickly release it when you reach your desired angle (nice how our RC models flit around and respond like they're on rails most of the time). Perhaps you should decide on a narrow range of aileron deflection (say between 50% and 75%) and adjust your aileron correction within that range based on the amount of roll angle error. In that example, the smallest aileron deflection you'd see would be 50%, until you are within some very close range of your desired bank angle, at which point you'd release the ailerons (depending on your model you would want some dampening code, to prevent "pilot"-induced oscillations...this could be something like what you're doing now, but with a little more sophistication).
Quick question: is your gyro (and other sensors) giving you absolute values, or relative values (ergo, relative to the previous cycle)?
Hope this gives you some ideas...I'm looking forward to exploring this area myself once I get into my own autopilot system!
Matt