It's not the motor specs that matter, assuming you're happy with how it runs from your 11V source. The issue is how much current this FEZ thing needs at what voltage.
A linear regulator should work well enough as long as the motor doesn't temporarily make the 11V supply dip so low that the regulator can't maintain the output voltage anymore.
In theory, a regulator puts out a constant voltage as long as the input voltage is above some threshold. If you're trying to get 5V or 3.3V, then 11V is plenty in that regard. However, in reality regulators can only cope with a certain speed of input voltage change. Motors can cause large and sudden spikes, which can get onto the regulated output to some extent even if the regulator input stays above its minimum threshold.
Fortunately the solution to both problems is simple. Put a diode followed by electrolytic storage cap between the 11V supply and the regulator input. That will prevent negative going spikes from making it to the regulator input. The capacitor will hold up the regulator input voltage for the short duration of any spike.
In a generally noisy environment like what you describe, it's a good idea to put some high frequency filtering in front of the regulator. I don't know how much current this FEZ thing draws, but if its just a micrcontroller at let's say 200mA, then a ferrite bead or "chip inductor" followed by 10uF ceramic cap right accross the regulator input and ground terminals will do fine. This will attenuate the high frequencies that the regulator is not so good at dealing with.
Another point is that a linear regulator will be rather inefficient in this application. Even if this FEZ thing wants 5V, that's still 6V it will drop for about 45% efficiency. That by itself may not be a big deal since the power wasted as heat may be small compared to what the motors use. It's probably more a issue of dealing with the heat. Again, that depends on the specs of the FEZ. If it draws 50mA at 5V, then the regulator will only dissipate 300mW. Not a big deal for a TO-220 case in free air. If on the other hand it draws 400mA at 3.3V, then the regulator will dissipate over 3W, which needs to be specifically dealt with.
It might therefore be worth looking into a switcher. At 80% efficiency it would only dissipate 330mW with 400mA at 3.3V out.
An important question to ask yourself: Can I really not access the cells' individual wires?
Your best option is accessing the wires to all the cells, usually battery packs have balancing connectors, with in it wires to connect to the joints of each set of cells.
This is done, because LiPo cells are much more sensitive to cell-to-cell imbalance and will waste away much faster if you do not check the cell balancing regularly, preferably each time you charge and/or discharge. Alternatively you also should make sure no single cell ever discharges below a level of about 2.5V.
The 4 cell chips do all of that for you, if you choose an appropriate one. They will stop current flow when any one of the cells is depleted, in stead of when the entire pack reaches a lower limit, and they should be chosen to have some balancing feature, to alow you to fully charge all the cells.
A 1 cell device will only work with one single cell, because it expects the upper limit of 4.25V and lower limit of 2.5V, connecting a full pack of 4 cells to its terminals will at best just not work, but most likely turn it into a ball of smoke.
Best Answer
If you think about how those wires are connected inside the battery pack, you will soon realize that when you connected all 3 wires together, you shorted out some of the cells inside the pack. You are right: this makes smoke.
Use the ground wire for ground and choose only the single hot wire that goes to the top cell. You will measure somewhere around 11.8V between that wire and the ground wire.
FWIW - you should charge your pack before you do anything else with it. Your charger will make sure that all the cells are balanced after the abuse you gave them.
Edit: Ignacio Vazquez-Abrams made the point that I forgot to make: you should consider using a switch-mode buck converter. You will be wasting more than half the available energy from your battery pack as heat if you stick with a linear regulator.