The biggest challenge in general is that the approach of storing every transaction forever leads to petabytes of storage. And you can't expect a decentralized system to require petabytes of storage.

I apologize if this a naive question but Proof of work is also decentralized no? Why does Proof of Stake incur these scaling limitations but Proof of work does not?

Both do.

Can you elaborate? The person I was replying to indicated that the problem was one of storage however the only scalability problems I have seen written about have been around transaction processing.[1]

[1] https://en.wikipedia.org/wiki/Bitcoin_scalability_problem

Not every node has to store every transaction ever. Nodes can prune old state