Maybe there is something under the bedliner preventing it from seating properly. I don't know how the stuff gets under there but about once a year I would take my liner off(and I had a shell on top) and clean all the debris- mostly leaves, twigs and small rocks.
It sounds like you have an "under-the-rail" liner. If you need to take it off just grab the back of the liner(from the
tailgate end) in the middle and lift. Most of it will pop-out from under the rail. The work on one side until it is completely out. The other side and back lip will just lift out. The liners don't weigh much (40-50lbs is my guess)but because of their shape they can be a bit unwieldy. Sometimes you need to muscle them around a little to get them to unseat.
Good luck
Tim