He conseguido solucionar el problema!! La solución (en NASM) es esta:

segment .text
	global _change_values
 
_change_values:
	enter 0,0
	push ebx
 
	mov edx, dword [ebp+8]
	mov ebx, dword [edx]     ; ebx = primer parámetro
	mov edx, dword [ebp+12]
	mov ecx, dword [edx]     ; ecx = segundo parámetro
 
	; mov dword [ebp+8], ecx   >> Intercambiador v1 NO FUNCIONA
	; mov dword [ebp+12], ebx 
 
	mov edx, dword [ebp+8] ; Intercambiador v2
	mov [edx], ecx
	mov edx, dword [ebp+12]
	mov [edx], ebx
 
	pop ebx
	leave
	ret
 

Esto me plantea otra duda. ¿Por qué el intercambiador v1 no funciona? Sé que le intercambiador v2 si que debe funcionar perfectamente (de hecho, funciona ), pero no entiendo porque en la primera versión que hice no puede funcionar...

Gracias por toda su ayuda!!

PD.: Sé que he puesto dword de sobra, pero aun quitándolos del intercambiador no funciona...

---

Aquí está la versión reducida (sinceramente, no sé si se puede optimizar más xD)

segment .text
	global _change_values
 
_change_values:
	enter 0,0
	push ebx
 
	; void intercambiar(int* valor_a, int* valor_b);
 
	mov eax, dword [ebp+8]  ; eax = value_a
	mov ebx, dword [ebp+12] ; ebx = value_b
	mov ecx, [eax]          ; ecx = *value_a
	mov edx, [ebx]          ; edx = *value_b
	mov [eax], edx          ; *valor_a = edx >> *valor_a = *valor_b
	mov [ebx], ecx          ; *valor_b = ecx >> *valor_b = *valor_a
 
	pop ebx
	leave
	ret
 

¡¡He caído dos veces en la misma trampa!! No me lo puedo creer... ¡QUE DURO ES APRENDER ASM! Pero es satisfactorio y útil