Thank you very much for the replies.
We are at the point where we must decide...
Delete the links and the guaranteed income.
Remove the the nofollow thing and risk losing our Google traffic (about 50% of our traffic).
Our traffic started to take an unusual dip around May 1st and we traced it to less traffic from Google though our rankings haven't changed as far as we can tell. This led me to research what may be the problem and all we could find were the paid links.
The question about the timeframe is more to determine if our Google traffic will continue to decrease since we made this change or will it be noticed and stop going down. If it goes back up, great, but we understand that we may need to earn back the traffic we had rather than have it magically reinstated.