Jennifer - since the likelihood of spilling paint rises exponentially to the damage it could do to that surface - I would say paint first.
For instance - we are doing a major kitchen re-do - including paint - but also a good deal of demolition. While we could do the new subfloor and flooring first - and cover it with rosin paper - it is easier not to care what happens to the old floor - since it is gone anyway....