Never mind, I actually found the answer somewhere else, after a bit more digging around. :)
It was indeed an incompatibility between the Gallery2 bridge and the SMF bridge (how they implement SEF).
I finally found the solution in
this thread (second post from top). (Note: change com_gallery to com_gallery2 in the fix, if that's what you're using.)
As Orstio said, the fix disables some bridge functionality in the com_gallery component, but in my case, I wasn't using it anyway so it was fine.
Just posting this in case anyone else was having the same problem.