I haven't used Box2d enough to necessarily say a huge amount, but for part of my capstone essay I linked Ogre and Bullet together... basically created the physics world, and then had the graphical world be based of of that. Why would you scale the physics off of the graphics?
From my experience, the purpose of graphics is to provide interactivity with a user, and as such you would only want to tweak those....
However, as I have been using a lot of libgdx recently, I am guessing it is something simple that is happening.
For the screen sizes, just adjust the camera viewport, and if need be clip the background texture depending upon what you are trying to do.
http://blog.acamara.es/2012/02/05/keep-screen-aspect-ratio-with-different-resolutions-using-libgdx/
http://www.badlogicgames.com/forum/viewtopic.php?f=11&t=1940
Much of specific graphic work depends entirely upon what you want to do with your game...
With your post, all I can really say at the moment is somewhat generic advice and link you to some stuff that I found when looking for help getting my backgrounds resized a while back... without having them or the foregrounds distorted... (for a fairly simple game with downloadable backgrounds).
Anyway, a summary of steps I would take to do this problem are as follows.
1. Make my physics world.
2. Set up my graphics world to match the physics world.
3. If need be, adjust graphics scale, or the camera.
4. If things are not hitting properly, research each library to make sure that the [x, y, z] coordinates that I have in my head are correct. (In the case of 2d, just [x,y]).
Example: Does Box2d start its physics body in the center for a ball, while my graphics are currently starting on the lower left [(x, y, width, height) vs (x - width / 2, y - height / 2, width, height)]. Without seeing the graphics code, which I would be reasonably familiar with, I am unable to give you a better idea for the research here...
5. If items appear squashed on screen, tweak the camera, maybe make extra graphics resources depending upon screen ratio, do more research into how my camera works, match up my demo application size with the camera size and see if everything looks good on the computer... if not, look into fixing distorted graphics.
Basically, if your window changes sizes, and you change the camera size to match that, and allow the view port to move, it will probably take care of all of your problems. As you are not basing the physics engine world off of the camera, it will mean that the physics all works right and you just have graphics to tweak.
Sorry if that was too rambling, I am somewhat tired right now and tend to ramble on at that point. I hope it makes sense....