Finally somebody else with this issue! For the last week or more, publishing has gone from a 30s process to a sometimes 30+ minute ordeal. Just like you said, it only seems to happen if overwriting an existing report/dataset. I've even had a few instances where publishing fails with an internal server error message (500). Also, Power BI desktop has randomly been signing me out when I try to publish.
It might be unrelated, but our dataflow refresh times have gone from 3 or 4 minutes to 2+ hours and even timing out at the 3 hour mark occasionally. I've tried updating Power BI desktop, and the data gateway to no effect.
Lastly, even browsing PowerBI.com has gotten slow periodically and won't load the workspace or reports.
Hopefully we can get some kind of offical word on this.