Did you try going to search charm and typing advanced printer setup and setting it up that way? I had to do this on both my desktop and Surface to get my new HP Envy 4505 to work. Works seamlessly now.
