I don't have any problems on S4, I got two near me, or any other phone (even SII).
Try to clean cache, it may be a problem with your device, or software/content additions (put only standard DEM file ~88MB, not premium), or whatever.