arcgis 10.0 - Delete SDE feature class features with ArcPy

I'm working on a script that will empty my SDE database of all data. How would I go about deleting features from feature classes using ArcPy?

I have an SDE connection created with a user that should have delete privileges. So far I've tried using the arcpy.DeleteFeatures_management from code and from the Delete Features toolbox in data management.

My DB has SDE feature datasets with SDE feature classes inside.

The Delete Features tool box errors out with:

ERROR 000732: Input Features: "Dataset Database Connections\Connection to sde.sde\User.MyFeatureDataset\User.MyFeatureClass" does not exist or is not supported.

The documentation is not really helping me. http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//001700000036000000