Assuming they meet the definition of MSB as a money transmitter...
You need to know more about each customer. IE Convienve stores offering this service are more likely to acting as Agents for an MSB.
A person that is an MSB solely because that person serves as an agent of another MSB is not required to register. However, a person that is an MSB both because it engages in MSB activities on its own behalf and as an agent of another MSB must register.
31 CFR 1022.380(a)(2) (formerly 103.41(a)(2))
Go to this link for more info.
http://www.fincen.gov/financial_institutions/msb/