Yup...more areas become available to you as you go though the storyline. In the previous 2 games, area restriction was done by surrounding it with water and disabling or blocking bridges across. But since you can swim in S.A., R* needed some other way. Hence, the automatic 4-star wanted level (the explaination given in the storyline is that Tenpenny wants to keep you around).
However, you can still visit such areas whenever you want to. This opens up an additional challenge in the game - by doing available side missions/tasks and obtaining collectables while such areas are still restricted. Getting all horseshoes in L.V. after it has been unlocked, for example, is a -really- boring task. Much more challenging to do it when police are gunning for you for leaving L.S.
Best way into such areas is probably via parachute. But this leaves you vulnerable right from the get-go. If you time it right, you can cause a hijacked train to pass right -through- the blockade, and have a virtually indestructable means of moving around the map. Just don't let cops climb aboard
If you wander too far away from the train, it will disappear...so an exit strategy is still needed in most cases. But it's a good way of getting close to an objective without losing health just to get there.
Go visit Unity or Market Station to hijack a train. Using a train engine that is towing THREE cars (type of cars and direction of travel does not matter), go all the way North through Las Colinas and into the hillside. Stop at the first tree you see once you emerge from that tunnel...then travel the opposite direction - keeping the button pressed thoughout. The engine will begin shaking (indicating imminent derailment) as you pass by the underground Market Station...but keep the hammer down all the way through Richman. Your velocity will be too high for the game to slow you down in time on appoach of the blockade...and you'll slide right through.
This trick can also be done with engines that are towing two or four cars, but you'll need to use a shorter or longer running distance.
If you are just after collectables (horseshoes, photo-ops, oysters), some early missions feature "wanted level exploits" to make that easier. At certian points of such missions, you are never given a wanted level no matter what you do...and so you are free to roam wherever you want while the exploit is active. A good one to experiment with is Sweet's mission "Drive-By". At the start of the mission, just take off instead of getting in the car (doing so kills the exploit).