Hi all!
Going to be doubly naughty by posting this a) to the wrong list (since Paleorecipes seems to be defunct) and b) without checking the archives for previous ideas like this.

Just the other day, I found what seems to me to be the perfect paleo foodstuff to substitute for sushi-rice in your nori-maki: seaweed! It's so obvious I've overlooked it ever since I went paleo the first time. Boiled and coursly chopped hijiki or arame with flavouring of your choice is simply beautiful with raw fish and vegetables. Try it - you'll like it!

Paleobest; Erik F.