I guess the discussion has since moved on, but I was just wondering if one of Paul's parents could have been a freed slave? In Rome a slave could become free through a ceremony called manumissio. The freed slave (called a liberi) did not have full rights and was obliged to work for their former master a set number of days each year as a client. However, any child born to the liberti would enjoy full Roman citizenship. Also if this was the case, could Rufus and his mother be the son and wife of the former slave master. If Paul was making regular visits accompanying his client parent to the former master he may have struck up a relationship with these people.
Anyway, just a suggestion don't know if it's plausible. By the way, not done any of this since school, got most of the details from
this wikipaedia article.