Cladistically, libertarianism comes out of the Left, not the Right, and in fact shares fairly close historical ties with socialism. This is obscured somewhat by the fact that modern libertarians talk a lot like modern conservatives and tend to use "socialist" as a loose secular synonym for "the spawn of he whom we call the Desolate One", but that's a trend that started no earlier than the Seventies or late Sixties.

For a simple counter-example, conservatives tend to love law and order, libertarians -- not so much.

True, there are some non-religious issues which separate conservatives and libertarians, but someone doesn't have to believe in every libertarian issue to be a libertarian. Are there enough prominent non-religious issues such that someone who takes a conservative position on only the non-religious issues would be considered closer to the conservative side than to the libertarian one?

A common simplistic understanding of libertarians is "conservative economically, liberal socially", but even then you don't get there from conservatives just by removing religion.

Don't you? Most issues where libertarians are socially liberal have the conservative side heavily influenced by religion.