menu_get_active_trail returns page not found
First, you have to make sure that the active menu is actually set. In Drupal 6, we did this like this: http://echodittolabs.org/blog/2010/04/drupal-fails-set-active-menu-trail-causing-context-fail.

Next, clear the cache, and then refresh the page. Yes, dpm() has a lag or something. If you see the right data, great.

My data was actually being cached as page not found, when actually it had set the correct data. Don't know why.

So, your debug info may show "Page not found" when, what is being rendered would be correct. The way you see if this is the case is by clearing the cache and refreshing.

This is for Drupal 6, but the principles likely hold for Drupal 7. Unfortunately, I doubt anybody rewrote the crufty old menu system. Too much AJAX and glitz.