Lion and Mountain Lion are usually downloads, and not generally on physical media.
Not all Mac systems are enabled for Internet Recovery. Here is a list of the supported systems. The Mid 2010 MacBook Pro 13" systems are supported, so your hardware should work. Which implies a problem with your local or upstream network connection, or with Apple's servers.
Given your network appears to be having problems (or Apple's servers are overloaded or flaky), you can use that other Mac to build an external boot disk (a recovery disk) using the recovery disk assistant), and then boot and install from that; more details.
It's also possible to generate a bootable DVD yourself, if the other Mac has a Lion or Mountain Lion download available, and a DVD drive that can record DVD media. Details on that sequence are posted at various sites; run a web search for the "InstallESD.dmg" discussions. Here's a CNET discussion for Lion, if that's what you were running.
In general, I'd recommend always having a backup, and also always having a local boot disk option available. Yes, these are obvious now, but these sorts of mistakes tend to catch most everybody — myself included — sooner or later.