Есть несколько проблем с тем, что вы написали. Основным является то, что метод Message.Replace заменит все пробелы в вашей строке первым сгенерированным случайным числом. Попробуйте разбить строку там, где есть пробелы, а затем соединить их со своими случайными числами между ними. Что-то вроде этого.
Dim RandomNumber As New Random()
Dim msg As String = "My name is Nick from Neptune"
Dim temp = msg.Split(CChar(" "))
Dim first As Boolean = True
For Each s As String In temp
If first Then
msg = s
Else
msg = msg + RandomNumber.Next(0, 33).ToString + s
End If
first = False
Next