IMHO, the most obvious problems with an interplanetary network are actually the least significant. When confronted with this idea, the immediate concern of most people is the same as when they are told about a new kind of broadband - how fast is it? Attempts to get rid of latency over interplanetary distances are futile, due to the very real and very unassailable lightspeed limit. The person who invents superluminal transmissions will be rich indeed, but it seems unlikely at the current level of technology. Thus, problem-solving should be directed towards overall usability and construction of a stable system, rather than a fast nippy one. Remember that the original ARPAnet could pump data at approximately walking speed (it was a joke amongst ARPA technicians that a letter could be delivered to an office faster by walking there than waiting for the network to chug it down at about ten words per second).
The more interesting problems as I see it are routing the signal from place to place and overall network integrity ie common reliability across the network. Routing is very difficult because planets move and rotate, and space-based satellites frequently break down or are damaged by space debris. Network integrity may be difficult to maintain under current network protocols, as a combination result of lightspeed limits and DNS servers that orbit each other.
Resolving the routing issue can be done in several ways, each with strengths and weaknesses. The idea here is to transmit information as quickly as possible, as efficiently as possible and with as much interactivity as is practical. As stated above, there is a very great invisibility issue, as our theoretical satellite-based relays would periodically disappear behind a misplaced planet, moon or giant nuclear fusion reaction. I must disagree with the suggestion of a non-ecliptic plane orbit. Although this would permanently solve the invisibility problem, there is a very good reason why all the planets orbit the sun along the same plane, based in the physics of circular motion. It is more energy efficient for matter to 'fall' down towards the ecliptic than to go back up. Furthermore, non-ecliptic plane orbits are unstable; every time they dip through the other planets' plane they are dragged about by the combined gravity. When you consider that the optimum orbital radius would be roughly that of Jupiter, the problem becomes more apparent.
Another option is to simply pepper the sky with satellites, having a GPS-like array around each planet, providing round-the-clock receiving ability for that planet. This is extremely inefficient, and in fact almost impossible once you get beyond our own hydrocarbon-rich world. Launching twenty satellites from a base no larger than (at best) a small town, without access to thirty million barrels of oil a day would prove very difficult and a waste of resources.
A simple and elegant solution is to develop a new DNS routing algorithm based on celestial mechanics. The current terrestrial mechanism is (as algorithms go) horrendously inefficient anyway, so there is a lot of leeway for an interplanetary replacement. Under this algorithm, every planet would have a central DNS-like server which maintained a constant internal orrery - a perfect map of where every network relay is positioned in the solar system. Since the movements of planets and satellites are governed very precisely by physics, this map would remain consistent, unless human intervention changed it. If Pluto wants to send a message to Neptune, which happens to be on the other side of the solar system, it simply consults its map and plots the most efficient route along the chain, taking tranmission lag into account. If the map is changed due to satellite breakdowns, this information could be quickly disseminated automatically by the servers, keeping everyone up to date. This is kind of like the very random 'check all the local servers and pass it on' system of current DNS, but more energy efficient due to the more precise nature of celestial mechanics and the far lesser number of possible relays.
Network integrity and useability, once again IMHO, cannot be attained using traditional request-response network theory. Distances are too great, lag too significant. I do not believe that current or even future technology would allow for web-like interaction. However, I do believe that with the use of compressed burst transmission (compression ratio goes up the more data you have at once) at scheduled times, any information requests could be honoured on a regular basis. So you make the request for information or send an email, it is stored in your planetary temporary store, and sent at the next scheduled interval in one big lump. At another interval, the scheduled burst from the nearest station would be received. Construction of the routing algorithm would be the greatest triumph of the whole affair, the rest of the system hangs on it like decorations on a christmas tree.