This change has been made and should be any random world map square that is still accessible by normal means (including lava, but excluding mountains/oceans/etc). If anyone finds this to not be the case, please post here or use the in game 'bug' command.