GPS is an 'incredible feat', that's advanced magic. This is many orders of magnitude more signal strength, even without beam steering. That said, it will still require a pretty sensitive receiver, but nothing on the order of what your cell phone already contains for GPS.

GPS receivers do not transmit information back to the satellites. Presumably these cell phone users will want two-way communication.

It's straight up, line of sight. The biggest issue will be water in the atmosphere. Compared to your average urban canyon it probably isn't all that bad.

Consider that HAMs routinely work insane distances with extremely little power LOS is relatively easy, especially if one side is a satellite with a beefy antenna for both transmission and reception. I'm more interested in the power budget than whether or not they can close the distance and what the effect is on the cell phone's battery life.

GPS receivers in a cell phone work at or under the noise floor, which to me is advanced magic. This will be way above that.

Line of sight will be needed for upload transmit, definitely. However, with sufficient power on the satelites it should be able to transmit loud enough at lower frequencies (better penetration) so it should be receivable inside of a phone pocket or underneath something shallow.

It will be interesting to see how well it performs inside structures. Is there any info on what kind of power those satellites can output or is that classified?

They said that the new satellites will included a roughly 25 square meter antenna dedicated for cell phones.