I bought Minecraft on my PS3, and have recently upgraded to a PS4. In my library on the store, it lists Minecraft as not installed, but when I go to install it, I have to pay for it. What is the problem, and is there any way to get around this?
Minecraft on PS3 and PS4 are two different games, so while you may own the PS3 version, you will have to pay again to get the PS4 version. Only games that support "Cross-Buy" can be bought once and played on different systems, but you will have to read up on what the game supports on the PlayStation Store.
Cross Buy games will usually have tags for [PS4] [PS Vita] where the game is supported on multiple platforms. Unfortunately, Minecraft is not one of them.
I don't know about Minecraft specifically, but the only PlayStation games that would allow you to do this would say in the game's description that you get both versions when purchased. Most such titles are for console and portable versions, I'm not aware of any PS3/PS4 ones. So, either buy the PS4 version of Minecraft or hook your PS3 back up.