Here is my CL with fix - https://codereview.chromium.org/1978793002

Thanks!  Nice find.  Repro steps in a debug build (based on your test):
1) Start at the new tab page.
2) Visit http://www.chromium.org.
3) In DevTools, run: location.replace("https://chrome.google.com/webstore/category/apps");
4) Go back (to the NTP), then go forward.

Step 3 forces a process swap on a navigation with replacement.  We apparently don't consider that a new navigation in the new process, so it never generates a page ID.

I was hoping this bug might help diagnose  issue 568703  as well, where we're crashing on the CHECK_EQ(request_params.page_id, -1) line of NavigateInternal.  This bug hits a different line, though:
DCHECK_NE(request_params.page_id, -1);

For reference, we'll probably be removing the rest of page ID soon ( issue 369661 , once I land the fix for  issue 577449 ), but it makes sense to correct this in the meantime.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/4b2ec6d51e135654911cc38d0193b221ac042a08

commit 4b2ec6d51e135654911cc38d0193b221ac042a08
Author: iceman <iceman@yandex-team.ru>
Date: Wed May 18 19:55:25 2016

RenderViewImpl::page_id_ isn't initialized for cross-process replacement
navigations.

There can be a situation, when |RenderViewImpl::page_id_| isn't initialized
for a navigation that should replace the current entry. And then it will
trigger a DCHECK in |RenderFrameImpl::NavigateInternal|.

It happens when a new page is loaded with |should_replace_current_entry| flag
set to true and a new renderer is used for this navigation (i.e. the new entry
uses a different SiteInstance from the previous entry's one).

BUG= 611679 
CQ_INCLUDE_TRYBOTS=tryserver.chromium.linux:linux_site_isolation

Review-Url: https://codereview.chromium.org/1978793002
Cr-Commit-Position: refs/heads/master@{#394515}

[modify] https://crrev.com/4b2ec6d51e135654911cc38d0193b221ac042a08/content/browser/frame_host/navigation_controller_impl_browsertest.cc
[modify] https://crrev.com/4b2ec6d51e135654911cc38d0193b221ac042a08/content/renderer/render_frame_impl.cc
[modify] https://crrev.com/4b2ec6d51e135654911cc38d0193b221ac042a08/content/renderer/render_view_browsertest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/c3bbb640c6513956b9fe9dc5e01baf5659019de0

commit c3bbb640c6513956b9fe9dc5e01baf5659019de0
Author: ahest <ahest@yandex-team.ru>
Date: Thu Sep 15 07:56:46 2016

Fix NavigationControllerBrowserTest.PageIDUpdatedOnPageReplacement.

Currently the test passes even without the original fix for  bug 611679 
(https://codereview.chromium.org/1978793002/patch/40001/50002).
I checked that this CL makes the test proper again (it fails without
the bug fix).

Discussed in https://codereview.chromium.org/2225053002/
(see most recent comments).

BUG= 611679 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_site_isolation

Review-Url: https://codereview.chromium.org/2339133002
Cr-Commit-Position: refs/heads/master@{#418801}

[modify] https://crrev.com/c3bbb640c6513956b9fe9dc5e01baf5659019de0/content/browser/frame_host/navigation_controller_impl_browsertest.cc

Issue has not been modified or commented on in the last 365 days, please re-open or file a new bug if this is still an issue.

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot