Yes, the brick feature is new. Though it shouldn't be placing stone brick ghosts if you don't have it! Oops.
You shouldn't have to deconstruct regular concrete. When the radius is fully paved, it will start looking for brick/concrete to upgrade and it will upgrade for you.