Yes, there is a space between deck and is.
deck:jacksparrow is:new
The above should not give any error.
If your deck name has spaces in it you would use something like:
deck:"Jack Sparrow Deck" is:new
Note the double (") quotes around the name.