I have never used it so I have no idea what would replace it. Was it cotton or alpha-cellulose? Bright or natural? What weight was it?
There are several 'velvet' papers around, most of them made by Somerset Mills in England. Moab has 225 g/mē and 255 g/mē Somerset Enhanced Velvet, Canon a 225 g/mē Fine Art Enhance Velvet, Epson a 260 g/mē Velvet Fine Art and a Somerset Velvet Fine Art Matte in 255 g/mē and 505 g/mē. There is also a Breathing Color Elegance Velvet that I have used when I need a really bright white, it is 310 g/mē. There are also several other textured matt papers that don't have the velvet label.
Your best chance would be buying several sample packs, and picking out the closest match.