Use iPhone 5s with total wireless

Hi everyone!

I bought an unlocked iPhone 5s at an Apple Store in California last year and have been using it in Germany with my carrier there. Now I'm back in the states and would like to use it with a plan from total wireless that goes through the Verizon network. The sales assistant at Walmart checked the IMEI number of my phone and said it wouldn't work.

I don't understand because I thought I bought an unlocked phone??? Shouldn't it work with any carrier?

Thanks for your help, I couldn't find anything on the Internet.

Jana