Your rule will look like this:
AND (
NOT(ISNEW()),
&&( ISPICKVAL(Order.Type ,'SO Regular Sales Order'),
&& OR(
ISPICKVAL(Line_Type__c ,'NONE'),
|| ISPICKVAL(Line_Type__c,'REC'))
)
)
Also, I think I can see an extra space 'SO Regular Sales Order ''SO Regular Sales Order '
at the end of this picklist value type.