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.
Brian A