I have an idea for a setting, but I need some help filling in gaps....

Summery; 20 Minutes into the Future (tech's a little better than it is now, but most improvements were in making it last longer) there's a huge disaster caused by a number of factors (economic meltdown, a few wars, climate change displacing some people) that causes large chunks of the world (including huge cities, etc) to be abandoned, with humans resettling in recently colonised areas (due to being previously uninhabitable) like deserts, the sea floor, underground cities, etc. While a lot of technology was lost, most of the knowledge was preserved. A few thousand years later, most of the technology has been rebuilt but in a roundabout way; since the records were damaged (and because of confusion) no one knows what was fiction and what was reality. The result is a mishmash of various aesthetics and mechanisms, with the technology someone uses being down to personal choice. For example some people have tried their best to build Steampunk technology (believing it was an actual predecessor to 21st century tech) on the grounds it would be "easier", others have tried to replicate fictional tech (either because they think it was real or they assume all science fiction was hard science fiction) and so on (with technology levels varying from roughly renaissance to 50's era technology). In addition many people use "SalvEque"; technology made from recovered artifacts that have been bodged together and combined with whatever local tech they need to make up the difference.

The main character(s) will be Adventure Archeologist types who are investigating the mid-21st century ruins.

Other quirks include; English and French have displaced Latin and Greek as scholarly languages (complete with pretentious mottos written in them with bad grammar), driving questions as to whether humanity ever colonised other words (or even there being a "lost tribe" on the moon), explorer-lawyers (who make their living tracking down and enforcing ancient ownership documents).

The problems I've got are;

• How should I have people treat records of "magic"?
• How would an economy in a world like this work (where the best technology has to be bodged together with whatever can be found)?
• What should the new world's government be like?
• How can I justify some of the older adventure tropes like traps and monsters in 21st century ruins?

What's the story about?

Something I'll work on when I've sorted out the setting (I really just want to do something in the style of a pulp novel; introduce hero, give hero problem, have him find and approach solution to problem, exciting climactic battle that solves said problem, or at least brings about a conclusion).

Respectfully, I think you've got the cart before the horse. I think you'll find that the needs of the plot will inform the setting, and unless you're planning to write a travelogue-style story like Les Mis or the first book of Fellowship of the Ring set in your fictional world (and you seem to want to write pulp adventure, so that doesn't seem to be your goal), most of the worldbuilding likely won't end up interacting with the plot anyway.

Kind of agree with A Man In Black here. Get at least the rudiments of a story first, or at least some kind of idea about themes and such. I know often I find that if I start out focusing on the setting too much at first, it's actually harder to find a story later, and it never gets off the ground. Figure out the story you want to tell and then mold the setting to assist in the telling.

Actually, you can start with your setting if that's how you work. With a well-developed setting you can come up with dozens of stories.

For government I'd have a patchwork of city-states. Undersea cities will have priorities different from cloud cities.

Have you considered having a patchwork of virtual environments? People will never know what's real and what's a hologram. That would let you use traps, monsters, advertisements, interactive fiction, etc.

I like this idea!

How about a dystopia. A seemingly peaceful haven, with dark secrets. Read The Giver to see what i mean (chances are, you already read it).

As for the economy, not quite sure. Maybe a world where in you have to scavenge to survive, or maybe some everyday item, that has become valuable, like the caps in Fallout 3.

For the justification, maybe you should add a little layer to the disaster story. An alternate timeline that can justify these, perhaps.

Maybe they can treat the records like some holy artifact, or something that is shunned by the public

You can base a story on a setting, but most authors don't. This is something I took a long time to learn, because I believed so strongly (and wrongly) that you need to have your world-building exactly right before writing, but actually, if you start with your story and develop your setting as you write, the world builds itself organically. You write what the character needs, and the writing goes much faster. If you feel strongly that you want to have a sense of layering and depth to the world (something I love in my favourite fantasy settings), you can add in references and foreshadowing when you edit. But that's after you've written the story, not before.