Is the phone set to LTE/CDMA /EVDO under Network Mode? It should be, as the default setting, but it's also possible to turn off LTE.
Sometimes I seem to have trouble getting 4G as well, but I know there is tower work in my area; the two zip codes nearest me have been listed as having outages on and off for over a month. I do get 4G at my workplace though - upstairs and in the parking lot, but not on the main floor - so I know the phone CAN receive it.