Finder in Mavericks will not tag files on network drives
I'm also having this problem. I've seen a few users comment on it on different forums and Apple's Support. No one has offered a real answer, other than this seems to be a problem with Apple's implementation of SMB or the way the Finder interacts and reads those Volumes (or the way attribute files are saved/stored/read on them).

The format of the servers volume doesn't really matter and should be transparent to the client. All Finder can see is a SMB share, whether that share is on an ext3 filesystem or a NTFS one is quite irrelevant.

I've tested connecting to the same volume with AFP, SMB (which in Mavericks now uses SMB2 by default) and CIFS (forcing Finder to use the SMB v1 protocol). As far as I know, tags info are stored in .DS_Store files for each folder.

Connecting with CIFS or SMB, tag support is buggy. Tags sometimes appear for a few seconds and then disappear. In addition to the .DS_Store file, a ._FILE_NAME file is created for each file. Getting the properties of the file sometimes shows the tag.

Connecting with AFP tags work as expected. Just a .DS_Store file is created. But no tag info is available if tag was assigned while mounted as SMB.

Is a pity, because SMB2 is faster than AFP in my tests, but sacrificing tags for it is too bad.