I can add a ShapeData with the name "herb:rest" if doing this manually with Visio.  When I try to do the same thing programmatically, a COM error is thrown (AddNamedRow method) that indicates the following exception:

System.Runtime.InteropServices.COMException was unhandled by user code
  HResult=-2032465656
  Message=

Cell names may consist of the characters a-z, A-Z, 0-9, and underscore symbol (_).
  Source=Drawing1 - Visio Professional
  ErrorCode=-2032465656
  StackTrace:
       at Microsoft.Office.Interop.Visio.IVShape.AddNamedRow(Int16 Section, String RowName, Int16 RowTag)
       at VisioPanelAddin3.visioStencilAccess.defineShapeProperty(Shape myShape, String shapeProperty, TheForm myForm) in c:\Users\root\Documents\Visual Studio 2012\Projects\VisioPanelAddin3\VisioPanelAddin3\visioStencilAccess.cs:line 95
       at VisioPanelAddin3.rdfsReader.loadRDFS(TheForm myForm) in c:\Users\root\Documents\Visual Studio 2012\Projects\VisioPanelAddin3\VisioPanelAddin3\rdfsReader.cs:line 71
       at VisioPanelAddin3.TheForm.updateStencilToolStripMenuItem_Click(Object sender, EventArgs e) in c:\Users\root\Documents\Visual Studio 2012\Projects\VisioPanelAddin3\VisioPanelAddin3\TheForm.cs:line 38
       at System.Windows.Forms.ToolStripMenuItem.OnClick(EventArgs e)
       at System.Windows.Forms.ToolStripItem.HandleClick(EventArgs e)
       at System.Windows.Forms.ToolStripItem.HandleMouseUp(MouseEventArgs e)
       at System.Windows.Forms.ToolStrip.OnMouseUp(MouseEventArgs mea)
       at System.Windows.Forms.ToolStripDropDown.OnMouseUp(MouseEventArgs mea)
       at System.Windows.Forms.Control.WmMouseUp(Message& m, MouseButtons button, Int32 clicks)
       at System.Windows.Forms.Control.WndProc(Message& m)
       at System.Windows.Forms.ToolStrip.WndProc(Message& m)
       at System.Windows.Forms.ToolStripDropDown.WndProc(Message& m)
       at System.Windows.Forms.NativeWindow.Callback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam)
  InnerException:

The offending line of code is:

  iRow =  myShape.AddNamedRow((short)Microsoft.Office.Interop.Visio.VisSectionIndices.visSectionProp, shapeProperty.ToString(), (short)Microsoft.Office.Interop.Visio.VisRowTags.visTagDefault);

Where shapeProperty has the value of "herb:rest".

The row gets added if just "rest" is used.

Is there a different call/code sequence that should be used?

Even manually the shape Name cannot be set to herb:rest, not by code either. Must be Alphanumeric + _

Are you setting the row Name or Label? The row Label can be almost anything.