I think there probably are practical problems besides just finding prime numbers that could be solved for the purpose of Bitcoin. There's no reason not to switch to that. It's probably just not a priority right now.
How much have you thought about it because it not a trivial problem.
A proof of work must have the following characteristics:
a) have an adjustable "difficulty" which works under a very large range (bitcoin difficulty is ~150,000,000x higher today than at genesis and likely will go another 10x to 100x over next year).
b) be very fast to verify (<100ms). Bitcoin has 52K blocks per year so someon bootstrapping 10 years after genesis woould need to validate 520K blocks in a timely manner.
c) the input of the proof must be linked to a prior proof to prevent precomputation (Bitcoin uses the prior block hash as input for current block hash to prevent solving "future" blocks).
d) the proof should be relatively compact (Bitcoin uses a 32 byte hash)
e) the solution should be probabilistic. This means that given two competitors and one has 10x the computing power the smaller competitor should find ~9% of the solutions. Many problems are not probablistic such that the faster competitor will always arrive at a solution first. That would be bad from a security standpoint.
f) require no outside "trusted" source or central authority for issuing or assigning work.
h) have a mechanism to prevent duplicated work across the network without any communication to a peer or outside data source.
Most simplistic "answers" fail this test. For example using folding@home would work as a proof of work as long as you are willing to have the administrators of folding@home be the central bank with complete control and authority over the currency.