The first dedicated search for ultra-high energy (UHE) tau neutrinos of astrophysical origin was performed using the IceCube detector in its 22-string configuration with an instrumented volume of roughly 0.25 km^3. The search also had sensitivity to UHE electron and muon neutrinos. After application of all selection criteria to approximately 200 live-days of data, we expect a background of 0.60 +/- 0.19 (stat.) $^{+0.56}_{-0.58}$ (syst.) events and observe three events, which after inspection emerge as being compatible with background but are kept in the final sample. Therefore, we set an upper limit on neutrinos of all-flavors from UHE astrophysical sources at 90% CL of $E^{2} Phi( u_{x}) < 16.3 * 10^-8 GeV cm^-2 sr^-1 s^-1 over an estimated primary neutrino energy range of 340 TeV to 200 PeV.