The informative part of the error is that the data you operating on is an S4 class object and as such contains slots. This means that you need to operate on the appropriate slot "@data" containing your dataframe.
If you want to delete "all" rows with NA values you can just use na.omit on the dataframe slot. This does propgate through the sp object and removes associated points/polygons in the other slots.
shape@data <- na.omit(shape@data)
If you want to remove rows with NA's in a specific column you can use:
shape@data <- shape[!is.na(shape@data$col) ,]
**** Update 03/08/2016
There is now a native merge function that operates on sp objects. You can call merge in the same way as you would with any other data.frame. However the x argument is a sp SpatailDataFrame class object and y is any data.frame that you want to merge. I am leaving the original answer for reference purposes.
I should also point out that you cannot use the merge function to join to an sp object. The merge function resorts the data during the operation which breaks the internal relationship in the sp object. This is something that is, unfortunately, not widely advertised. To merge a dataframe to the @data slot of an sp object you can use match in this way.
shape@data = data.frame(shape@data, OtherData[match(sdata@data$IDS, OtherData$IDS),])
Where; shape is your shape file, IDS is the identifier you want to merge on and OtherData is the dataframe that you want to combine with shape. Note that IDS can be different names in the two datasets but need to actually be the same values (not fuzzy).
Alternatively you can use this function.
join.sp.df <- function(x, y, xcol, ycol) {
x$sort_id <- 1:nrow(as(x, "data.frame"))
x.dat <- as(x, "data.frame")
x.dat2 <- merge(x.dat, y, by.x = xcol, by.y = ycol)
x.dat2.ord <- x.dat2[order(x.dat2$sort_id), ]
x2 <- x[x$sort_id %in% x.dat2$sort_id, ]
x2.dat <- as(x2, "data.frame")
row.names(x.dat2.ord) <- row.names(x2.dat)
x2@data <- x.dat2.ord
return(x2)
}
Where; x=sp SpatialDataFrame object, y=dataframe object to merge with x, xcol=Merge column name in sp object (need to quote), ycol=Merge column name in dataframe object (need to quote).
For some reason I cannot comment on @Kelly question so I am editing my original answer. Check what version of R and sp are you running? You can run SessionInfo() to find out. The behavior of removing associated objects in the other data slots when manipulating the @data object has only been available in the last couple sp versions. If not running a current version try updating the package with "Update packages" under the packages menu. If running >=Windows Vista be sure to run as administrator. Also look at your before and after object dimensions i.e., dim(shape), which represents the number of rows/cols. The number of rows corresponds with the number of feature objects. You can gut check the results by checking to see if the number of rows in the spatial object match the number of rows in the @data slot i.e., dim(shape); dim(shape@data)