Yes, but it depends on your level of timekeeping technology.
Magnetic North and True North are not the same, nor are they even close when you get near the poles. The magnetic field of the Earth varies over time, and will even undergo complete reversals (where the North magnetic pole moves to the South true pole and vice versa).
The difference between Magnetic and True north is known as magnetic variation (or MAGVAR for short), and must be accounted for in navigational charts, which are published periodically.
Right now, the Earth is likely (there is much scientific debate about it) approaching another rapid reversal in its poles, and it is possible (though unlikely) in the next 100 years the North and South magnetic poles could change position.
During a pole reversal, it is possible for the magnetic field to develop multiple north and south poles all over the surface, or even for the field to collapse entirely. We haven't seen this yet, but there are a lot of variations in the Earth's magnetic field, and even a possible new South Magnetic pole forming at what is known as the "South Atlantic Anomaly" off the coast of Argentina.
Similarly, the North Magnetic pole is wandering very rapidly, by up to hundreds of kilometers per year. Because of this, anywhere above roughly 60 degrees of latitude, navigating strictly by magnetic compass without knowing the current magvar for your location is extremely unreliable (luckily we rarely use magnetic compasses these days).
So it is entirely possible for the scenario you describe to occur. In this case, magnetic navigation would be completely unreliable, but all isn't lost, depending on your technology.
As some have mentioned, a sextant allows one to navigate very accurately by the stars, but there is a snag: It requires an extremely accurate clock to do so. Sextants work by measuring the horizon angle to a certain star at a certain time. This can give you both your latitude and longitude using charts. The British Royal Observatory in Greenwich was established partially for the purpose of creating these charts, and was invaluable to international navigation during Victorian times. In fact, the calculations for determining your latitude and longitude are based on the longitude of the Royal Observatory (defined as 0), and the charts published by the Observatory are essentially the time that one can expect a given star to rise on a given date at the Observatory's location. By doing a little trigonometry and comparing the local times at your location for the same star (using a sextant and clock), you can nail down your position to the accuracy of your clock.
Since the accuracy of your location is directly tied to the reliability of your clock, a great deal of effort was put into advancing timekeeping technology, and arguably, these increasingly accurate clocks are what enabled Europe to expand their seagoing empires and create some of the most powerful navies in the world.
Perhaps appropriately, today the most accurate atomic clocks that generate the standard time for the world are generally managed by the most powerful navies in the world. A prime example of which being the the US Naval Observatory which provides the "Master Time" for the United States from dozens of atomic clocks, which themselves are a part of the International Atomic Time standard (which gives rise to Coordinated Universal Time).