Pages appear as 404 even when PHP files are present

[Omega Prime]

Since I've been trying to figure this out since the 8th, I hope someone here can answer this:

I upgraded to vB3.6 Beta 1 on June 8th. My gallery and arcade didn't load, but it wasn't a huge deal at the time since I assumed it was merely an incompatibility issue. Days later, Beta 2 was released and those products still didn't work. Whenever I tried loading the pages, they only showed up as 404 errors, even when the files/templates are there.

Today, I ran the gallery thru the validator and it does seem to find the page, even though it appears missing to me. I'm quite sure it's a PHP issue, yet I've never heard of this issue til now. If anyone here knows about this or how to fix it, it'd be highly appreciated!

Edit: I disabled GZip in the admincp and things worked again